Explained tabulation dynamic programming.
Intuition\n Describe your first thoughts on how to solve this problem. \n\nYou are given an integer array nums with length n.\n\nThe cost of a subarray nums[l..
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nYou are given an integer array `nums` with length $$n$$.\n\nThe cost of a subarray `nums[l..r]`, where $$0 \\leq l \\leq r < n$$, is defined as:\n\n$$\\text{cost}(l, r) = nums[l] - nums[l + 1] + ... + nums[r] \\times (\u22121)^{r \u2212 l}$$\n\nOr in fully mathematic notation, it will be\n\n$$\\text{cost}(l, r) = \\sum_{i=l}^{r} \\text{nums}[i] \\times (-1)^{i-l} $$\n\nElements at **even** indexes (i.e. 0, 2, 4, 6, ...) in subarray would be subtracted in the cost calculation, and the ones at **odd** indexes (i.e. 1,3,5,7,...) will be added.\n\nThe total cost is sum of costs of all subarrays. In this problem, we are asked to get max possible cost by splitting the array into several subarrays.\n\nThus, we need to do this in splitting to gain maximized total cost:\n\n- If the element is **positive** or zero, split it to a subarray directly to ensure it placed at 0-th index.\n- If the element is **negative**:\n    - If current element is the second element of `nums` (`nums[1]`) or _its previous element_ is positive or zero, merge it to the previously created subarray. So it would be placed at index 1.\n    - Otherwise, pick the max possible cost from the possible splits.\n        For example, array `[1,-3,-2]` can be splitted to :\n        1. `[1,-3]` and `[-2]`, that costs `(1 - (-3)) + (-2) = 2`, which equals to cost of `[1,-3,-2]`.\n        2. `[1]` and `[-3,-2]`, that costs `1 + (-3 - (-2)) = 0`\n\nSince we need to use previous values on the process (in consecutive negative elements case), we can use up tabulation / bottom-up dynamic programming.\n\nSimilar problem, but simpler = [House Robber](https://leetcode.com/problems/house-robber/description/)\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\n1. If $$n == 1$$, return `nums[0]` directly. No need to do more calculation.\n2. Create a new array sized $$n$$ to store the total costs of subarrays from `nums[0..i]`. Because we need to revisit the previous elements `nums` to check its sign (positive / negative).\n3. Initialize the tabulation by setting:\n    ```\n    dp[0] = nums[0]\n    ```\n4. For `i=1` to `i=nums.length-1`:\n    1. If `nums[i] >= 0`, add it immediately. Let\'s assume that we created new subarray.\n        ```\n        dp[i] = dp[i-1] + nums[i]\n        ```\n    2. Else:\n        1. If `i==1 || nums[i-1] >= 0`, merge it directly to the last created subarray. When `i==1`, there\'s no better choice to make the cost bigger, than merging this element to be added. *Elements on even indexes will be subtracted.*\n            ```\n            dp[i] = dp[i-1] - nums[i]\n            ```\n        2. Else, This is consecutive negative elements, so we need to recalculate for the optimal splits. In this step, we have our latest subarray: `[nums[i-2], nums[i-1]]`.\n            ```\n            dp[i] = max(\n                        // Merge directly to latest subarray\n                        // cost([nums[i-2], nums[i-1], nums[i]])\n                        dp[i-1] + nums[i], \n\n                        // Split the latest subarray into 2, then\n                        // merge this element to the one containing nums[i-1]\n                        // cost([nums[i-2]]) + cost([nums[i-1], nums[i]])\n                        dp[i-2] + nums[i-1] - nums[i]\n                    )\n            ```\n\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        if(nums.length == 1) return nums[0];\n\n        long[] dp = new long[nums.length];\n        dp[0] = nums[0];\n\n        for(int i=1; i<nums.length; i++) {\n            if(nums[i] >= 0) {\n                dp[i] = dp[i-1] + nums[i];\n            } else {\n                if(i==1 || nums[i-1] >= 0) {\n                    dp[i] = dp[i-1] - nums[i];\n                } else {\n                    dp[i] = Math.max(dp[i-1]+nums[i], dp[i-2]+nums[i-1]-nums[i]);\n                }\n            }\n        }\n\n        return dp[nums.length-1];\n    }\n}\n```
['Dynamic Programming', 'Java']