Straightforward DP solution with concise explanation. Time O(n) and Space O(1).
Intuition\nIt is a dynamic programming problem. Each element in the input will be either taken as is or taken with a flipped sign in the final cost. \n\n# Appro
# Intuition\nIt is a dynamic programming problem. Each element in the input will be either taken as is or taken with a flipped sign in the final cost. \n\n# Approach\nWe can assume that DP_p[i] is the maximum cost of the arry [0, i] with the number at index i taken as is and DP_p[i] is the maximum cost of the arry [0, i] with the number at index i taken with a flipped sign.\n\nThen we will have the following induction rule:\n\n**Case 1**: the number at position is taken as is. It doesn\'t matter what sigan the previous number is taken.\n\nDP_p[i] = max(DP_p[i-1], DP_n[i-1]) + nums[i]\n\n**Case 1**: the number at position is taken with a flipped sign. Thi case, we can only combine this number with its previous number and its previous number is taken as is then we could have nums[i-1] - nums[i] such that the sign of nums[i] is flipped in the cost calculation.\nDP_p[i] = DP_p[i-1] - nums[i]\n\n**Base case**: We can only take the first number as is.\nDP_p[0] = nums[0]\nDP_n[0] = nums[0]\n\n**Return** max(DP_p[n - 1], DP_n[n - 1]) where n is the size of the input.\n\nPlease note that the calclation of DP_p[i] and DP_n[i] only rely on (i-1)\'s result which means we just need to record its previous result. So we can use rolling array to reduce the space complexity to constant.\n\n# Complexity\n- Time complexity: $$O(n)$$\n\n- Space complexity: $$O(1)$$\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        if (nums.empty()) {\n            return 0;\n        }\n        long long kept_p = nums[0];\n        long long kept_n = nums[0];\n        for (int i = 1; i < nums.size(); ++i) {\n            long long previois_kept_p = kept_p;\n            kept_p = max(kept_p, kept_n) + nums[i];\n            kept_n = previois_kept_p - nums[i];\n        }\n        return max(kept_p, kept_n);\n    }\n};\n```
['C++']