C++/Python3/Java Solution | Beats 100% | 4 Line ✔️
Intuition\nUpon first glance, the problem seems to involve a pattern of alternating +ve and -ve signs. It appears as if we start with a positive sign and altern
# Intuition\nUpon first glance, the problem seems to involve a pattern of alternating `+ve and -ve signs`. It appears as if we start with a positive sign and alternate signs thereafter, and we can switch all the subsequent signs if the current sign is negative. To maximize the cost, we need to determine the optimal positions where we can swap signs. Considering all possibilities, the time complexity would be $$\uD835\uDC42(2^\uD835\uDC5B)$$.\n\nHowever, a closer examination reveals that we can simplify our approach by considering two cases: treating the current element\'s sign as positive or negative and maintaining its maximum value accordingly.\n\nWe just need to store the maximum value of cost upto current element where the subarray ends with `+ve` or `-ve` sign and calculate the value of thereafter based on current `+ve` and `-ve` sign value.\n\nHere\'s how the signs of the previous element should align in these two cases:\n\n- Current element as `+ve`: The previous element can either be `+ve` (if we start a new subarray) or `-ve` (if we continue the current subarray).\n- Current element as `-ve`: The previous element must be `+ve` to maintain the alternating sign pattern.\n\n# Approach\n`a` and `b` are the value of maximum cost of nums from 0 to current element ending with `+ve` and `-ve` signs respectively.\n\n# Complexity\n- Time complexity: $$O(n)$$\n- Space complexity: $$O(1)$$\n\n# Code\n\n```python3 []\nclass Solution:\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        a, b = -inf, 0\n        for i in nums:\n            a, b = max(a, b) + i, a - i\n        return max(a, b)\n```\n```C++ []\nclass Solution {\npublic:\n    long long maximumTotalCost(vector<int>& nums) {\n        long long a = INT_MIN;\n        long long b = 0;\n        for(int& i: nums) {\n            long long c = a;\n            a = max(c, b) + i;\n            b = c - i;\n        }\n        return max(a, b);\n    }\n};\n```\n```java []\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        long a = Integer.MIN_VALUE;\n        long b = 0;\n        for (int i : nums) {\n            long c = a;\n            a = Math.max(c, b) + i;\n            b = c - i;\n        }\n        return Math.max(a, b);\n    }\n}\n```\n\n
['Dynamic Programming', 'C++', 'Java', 'Python3']