Beats 100%, Intuitive approach with explanation, in python
Intuition\n\nEach element will either have a positive multiplier (+1) or a negative multiplier(-1). We just need to consider multiplier sign of an element, with
# Intuition\n\nEach element will either have a positive multiplier (+1) or a negative multiplier(-1). We just need to consider multiplier sign of an element, with regard to the multiplier sign of the previous element:\n- If the previous element is negative multiplied, then current has to be positive multiplied\n- If the previous element is positive multiplied, then current can be either positive or negative multiplied.\n\n# Approach\n\nRewriting the above intuition for current element:\n- For current element to be negative multiplied, we need to consider only previous element positive multiplied case\n- For current element to be positive multiplied, we can consider best of previous element negative and positive multiplied\n\nHence, we get this DP relation\n```\ndpNeg[i] = dpPos[i-1] - nums[i]\ndpPos[i] = max(dpNeg[i-1] + nums[i], dpPos[i-1] + nums[i])\n```\n\nWhere we initialise both dpNeg and dpPos with nums[0], as first element has to be positive multiplied in any case.\n\nNote: Corner case of len(nums) = 1 is automatically handled with dp initiliasation and loop range  \nNote: We don\'t need to store the whole dp array, we just need the last value of the dp (saving on space complexity)\n\n# Complexity\n#### Time complexity: O(n)\nWe solve this in a single pass of the nums array\n\n#### Space complexity: O(1)\nWe use just two extra variable to store the negative and positive DP values\n\n# Code\n```python\nclass Solution:\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        dpPos = nums[0]\n        dpNeg = nums[0]\n        for i in range(1, len(nums)):\n            oldDpPos = dpPos\n            dpPos = max(dpNeg + nums[i], dpPos + nums[i])\n            dpNeg = oldDpPos - nums[i]\n        return max(dpNeg, dpPos)\n```
['Dynamic Programming', 'Python3']