Detailed explanation using 1D dp
Intuition\nThe idea is to use dynamic programming.\n\n# Approach\nLet dp[i] stores the answer to the array from [i...n - 1] where n is the size of the array. Ou
# Intuition\nThe idea is to use dynamic programming.\n\n# Approach\nLet dp[i] stores the answer to the array from [i...n - 1] where n is the size of the array. Our answer will be $$dp[0]$$. \n\n# Observation\nIt is never necessary to partition the array into size more than 2. In other words the size of the partition will either be 1 or 2. The reason is we want to have more and more positive numbers in the array. If the number is already positive then we separate that out into a subarray of size 1. If the number is negative then to make it positive we have to start creating the subarray from one element before eat. For example if array is $$[1, -2, 3, -4]$$ then the optimmal answer will be $$[1 + -1*(-2) + 3 + -1*(-4)]$$ because it makes both $$-2$$ and $$-4$$ positive. But the same result can also be achieved by making splitting the array into $$[1, -2]$$ and $$[3, -4]$$. Hence as soon as we make a -ve number positive we need not worry about whats ahead of it. \n\n## Recurrence\nThe $$dp[i]$$ state would go like:\n$$p1 = arr[i] + dp[i + 1]$$ taking $$arr[i]$$ into a separate subarray\n$$p2 = arr[i] + (-1*arr[i + 1]) + dp[i + 2]$$ changing sign of $$arr[i + 1]$$\n\n$$dp[i] = max(p1, p2)$$\n \n\n# Complexity\n- Time complexity: $$O(n)$$ \n\n- Space complexity: $$O(n)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        int n = nums.size(), i;\n        vector<long long> dp(n + 1);\n        dp[n - 1] = nums.back();\n        for(int i = n - 2; i >= 0; --i) {\n            long long p1 = nums[i] + dp[i + 1];\n            long long p2 = nums[i] + (-1) * nums[i + 1] + dp[i + 2];\n            dp[i] = max(p1, p2);\n        }\n        return dp[0];\n    }\n};\n```
['C++']