[Java/Python 3] DP O(n) codes, from space O(n) to O(1).
Except nums[0], we can always choose an item in the input either as original value, or flip its sign plus keep previous item as original value, and there is no 
Except `nums[0]`, we can always choose an item in the input either as original value, or flip its sign plus keep previous item as original value, and there is no other options; Therefore, starting from `i = 1, nums[i]`, our state transition function is `dp[i + 1] = max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]`.\n\n\n```java\n    public long maximumTotalCost(int[] nums) {\n        int n = nums.length;\n        long[] dp = new long[n + 1];\n        dp[1] = nums[0];\n        for (int i = 1; i < n; ++i) {\n            dp[i + 1] = Math.max(dp[i] + nums[i], dp[i - 1] + nums[i - 1] - nums[i]);\n        }\n        return dp[n];\n    }\n```\n\n```python\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        dp = [0, nums[0]]\n        for x, y in pairwise(nums):\n            dp.append(max(dp[-1] + y, dp[-2] + x - y))\n        return dp[-1]\n```\n\n**Analysis:**\nTime: O(n), space: O(n).\n\n----\n\nSpace Optimization:\n\nSince each value in `dp` array depends at most previous `2` items, we only need a `dp` array of size `3`.\n\n```java\n    public long maximumTotalCost(int[] nums) {\n        long[] dp = {0, nums[0], 0};\n        for (int i = 1; i < nums.length; ++i) {\n            dp[(i + 1) % 3] = Math.max(dp[i % 3] + nums[i], dp[(i - 1) % 3] + nums[i - 1] - nums[i]);\n        }\n        return dp[nums.length % 3];\n    }\n```\n\n```python\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        dp, n = [0, nums[0], 0], len(nums)\n        for i in range(1, n):\n            dp[(i + 1) % 3] = max(dp[i % 3] + nums[i], dp[(i - 1) % 3] + nums[i - 1] - nums[i])\n        return dp[n % 3]\n```\n\n**@xxxxkav** provided more readable codes as follows:\n\n```java\n    public long maximumTotalCost(int[] nums) {\n        long[] dp = {0, nums[0]};\n        for (int i = 1; i < nums.length; ++i) {\n            dp = new long[]{dp[1], Math.max(dp[0] + nums[i - 1] - nums[i], dp[1] + nums[i])};\n        }\n        return dp[1];\n    }\n```\n```python\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        dp = (0, nums[0])\n        for x, y in pairwise(nums):\n            dp = (dp[1], max(dp[0] + x - y, dp[1] + y))\n        return dp[1]\n```\n**Analysis:**\nTime: O(n), space: O(1).\n
['Dynamic Programming', 'Java', 'Python3']