Easy to understand DP | O(n) beats 100%
Intuition\nKey idea: All subarrays will either be of length $1$ or length $2$. This is because any subarray length greater than $2$ can be made with various sub
# Intuition\n**Key idea:** All subarrays will either be of length $1$ or length $2$. This is because any subarray length greater than $2$ can be made with various subarrays of lengths $1$ and $2$, and the sum of the scores of these smaller subarrays will be $\\geq$ the score of the larger subarray.\n\nNow, we simply have to figure out when to create a new subarray (*add* the current element to the total), and when to continue an existing subarray (*subtract* the current element from the total).\n\n# Approach\n\nWe use dynamic programming to solve this problem. The DP state is defined as:\n\n- `dp[i][0]`: Maximum total cost up to index i, ending with a subarray of length 1\n- `dp[i][1]`: Maximum total cost up to index i, ending with a subarray of length 2\n\nFor each element, we have two choices:\n1. Start a new subarray (length 1)\n2. Continue the previous subarray (length 2)\n\n### DP Transitions\n\n1. For starting a new subarray:\n   `dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + nums[i]`\n   We take the maximum of the previous states and add the current element.\n\n2. For continuing the previous subarray:\n   `dp[i][1] = dp[i-1][0] - nums[i]`\n   We can only continue from a state that ended with a length 1 subarray, and we subtract the current element due to alternating signs.\n\n### Base Case\n\nWe initialize `dp[0][0] = dp[0][1] = nums[0]` as the first element can be considered both as a length 1 subarray and the start of a longer subarray.\n\n\n# Complexity\n- Time complexity:\n$O(n)$\n\n- Space complexity:\n$O(n)$\n\n# Code\n```\nclass Solution:\n    def maximumTotalCost(self, nums: List[int]) -> int:\n        n = len(nums)\n        dp = [[0, 0] for _ in range(n)]\n        \n        # base case \n        dp[0][0] = nums[0]\n        dp[0][1] = nums[0]\n        \n        for i in range(1, len(nums)):\n            # state 1: create a new subarray\n            dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + nums[i]\n            # state 2: continue the previous subarray\n            dp[i][1] = dp[i-1][0] - nums[i]\n        \n        return max(dp[n-1][0], dp[n-1][1])\n```
['Dynamic Programming', 'Python', 'Python3']