Dynamic programming and space optimized. Beats  100%, easy to understand.
Intuition\n Describe your first thoughts on how to solve this problem. \nKind of dynamic programming\n\n# Approach\n\nFor each number we have 2 choices, add or 
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nKind of dynamic programming\n\n# Approach\n\nFor each number we have 2 choices, add or subtract to previous result.\nWe will maintain 2 result states, **addResult** and **subResult**.\n\nNow coming to current element, if we want to\n- **Add**: We can add this to maximum of addResult and subResult, because previous result doesn\'t matter.\n- **Subtract**: We need to add this to addResult, because adding it to subResult will make it more negative as well as it violates problem statement;\n\nOnce we are done with all element, return maximum of addResult and subResult\n         \n<!-- Describe your approach to solving the problem. -->\n\n# Complexity\n- Time complexity: $$O(n)$$\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: $$O(1)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Java\n```\nclass Solution {\n    public long maximumTotalCost(int[] nums) {\n        int n = nums.length;\n        long addResult = nums[0];\n        long subResult = nums[0];\n        for (int i = 1; i < n; i++) {\n            long tempAdd = Math.max(addResult, subResult) + nums[i];\n            long tempSub = addResult - nums[i];\n\n            addResult = tempAdd;\n            subResult = tempSub;\n        }\n        return Math.max(addResult, subResult);\n    }\n}\n```\n\n#Python\n```\ndef maximumTotalCost(self, nums):\n    add_result = nums[0]\n    sub_result = nums[0]\n\n    for i in range(1, len(nums)):\n        temp_add = max(add_result, sub_result) + nums[i]\n        temp_sub = add_result - nums[i]\n\n        add_result = temp_add\n        sub_result = temp_sub\n\n    return max(add_result, sub_result)\n```\n\n\n
['Dynamic Programming', 'Java', 'Python3']