Kotlin | Dynamic Programming | Iterative | O(n) time | O(1) space
1. DP array\n\nfun maximumTotalCost(nums: IntArray): Long {\n    val dp = LongArray(nums.size + 1)\n\n    for (i in nums.lastIndex downTo 0) {\n        dp[i] = 
# 1. DP array\n```\nfun maximumTotalCost(nums: IntArray): Long {\n    val dp = LongArray(nums.size + 1)\n\n    for (i in nums.lastIndex downTo 0) {\n        dp[i] = nums[i].toLong() + dp[i + 1]\n\n        if (i < nums.lastIndex) {\n            dp[i] = maxOf(dp[i], (nums[i] - nums[i + 1]).toLong() + dp[i + 2])\n        }\n    }\n\n    return dp[0]\n}\n\n```\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(n)$$\n\n# 2. Space optimization\nWe may see that at each iteration we are only using results from 1 and 2 steps before. Thus, we can use just 2 variables for this, instead of array.\n```\nfun maximumTotalCost(nums: IntArray): Long {\n    var max = Long.MIN_VALUE\n    var prev = 0L\n    var prevPrev = 0L\n\n    for (i in nums.lastIndex downTo 0) {\n        max = nums[i].toLong() + prev\n\n        if (i < nums.lastIndex) {\n            max = maxOf(max, (nums[i] - nums[i + 1]).toLong() + prevPrev)\n        }\n\n        prevPrev = prev\n        prev = max\n    }\n\n    return max\n}\n```\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$
['Kotlin']