Kotlin | O(n) time, O(n) space | DP | explained  (655ms, 161MB)
Intuition\n\nThe problem is equal to "you can change any two consequent items from a, b to a, -b multiple times (or zero), but each original item could be chang
# Intuition\n\nThe problem is equal to "you can change any two consequent items from `a, b` to `a, -b` multiple times (or zero), but each original item could be changed only once. Maximize the sum of items."\n\n# Approach\n\nDynamic programming:\n\n- $$maxCost[0] = nums[0]$$\n- $$maxCost[i] = max\\left( maxCost[i-1] + nums[i], maxCost[i-2] + nums[i-1] - nums[i] \\right)$$\n    - we either pick an item as-is or apply `a, -b` pattern\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(n)$$  (non-iterative impl with caching)\n\n# Code\n```\nimport kotlin.math.max\n\n\nclass Solution {\n\n    private var cache: Array<Long?> = emptyArray()\n\n\n    fun maximumTotalCost(nums: IntArray): Long {\n        cache = arrayOfNulls(nums.size)\n        return maxCostUptoIdx(nums, nums.size-1)\n    }\n\n    private fun maxCostUptoIdx(nums: IntArray, i: Int): Long {\n        return when {\n            (i < 0) -> 0L\n\n            (i == 0) -> nums.first().toLong()\n\n            else -> {\n                if (cache[i] != null) {\n                    cache[i]!!\n                } else {\n                    val result = max(\n                        maxCostUptoIdx(nums, i - 1) + nums[i],\n                        maxCostUptoIdx(nums, i - 2) + nums[i - 1] - nums[i]\n                    )\n                    cache[i] = result\n                    result\n                }\n            }\n        }\n    }\n\n}\n\n```
['Dynamic Programming', 'Kotlin']