[Beats 100%] 4 approaches HOW TO BUILD UP TO OPTIMAL SOLUTION + Full thought process
Approach\nThe goal is to maximize the sum of alternating subarrays.\n\nAn alternating subarray starts by adding the first element, then subtracts the 2nd, adds 
# Approach\nThe goal is to maximize the sum of alternating subarrays.\n\nAn alternating subarray starts by adding the first element, then subtracts the 2nd, adds the third, etc.\nIn other words, add up all the even indices and subtract the odd ones.\n\nThe first thing to do is look at the constraints. Solutions TLE around 10<sup>10</sup>, so with input length 10<sup>5</sup>, we need a linear or linearithmic (nlogn) solution to pass.\n\n\nYou can try to maximize elements included in even subarrays or minimize the odds, but they may disagree.\nYou can try greedy, but then a locally optimal decision may not be globally optimal.\nThis analysis is a good indicator that the best score at a position must depend on subproblems to get a globally optimal result.\n\nAt this point, dp/recursion seems like our best bet. The recurrence relation isn\'t too complicated: just take the max of extending an array or starting a new one\n\nHere\'s a basic outline of what that looks like:\n```python3\n@cache\ndef find_max(pos, cur_subarray_start):\n    parity = 1 if ((pos - cur_subarray_start) % 2 == 0) else -1\n    extend_subarray = nums[pos] * parity + find_max(pos + 1, cur_start)\n    new_subarray = nums[pos] + find_max(pos + 1, pos + 1)\n    return max(extend_subarray, new_subarray)\n```\nThis is where the problem gets tricky. The above code is $O(n^2)$ and it\'s not immediately obvious how to make it linear.\n\n**Key Insight**: We only need the position of the current subarray start to determine parity. Therefore, we can simply pass in parity as the 2nd argument.\nThen, we make at max 2 calls at each position, meaning we have linear time complexity. If this is confusing, think about the size of the memoization table. It\'s now $O(2n)$ because there could be a True and False for each item.\n\nWith this insight, we can form a working solution:\n```python3\n# TC: O(n)\n# SC: O(n)\ndef maximumTotalCost(self, nums: List[int]) -> int:\n    n = len(nums)\n    dp = {}  # dp[i] = best score up to i\n    \n    def form_subarrays(pos, is_even):\n        if (pos, is_even) in dp:\n            return dp[(pos, is_even)]\n        \n        if pos == n:\n            return 0\n        \n        extend_subarray = nums[pos] * (1 if is_even else -1) + form_subarrays(pos + 1, not is_even)\n        new_subarray = nums[pos] + form_subarrays(pos+1, True)\n        dp[(pos, is_even)] = max(extend_subarray, new_subarray)\n        return dp[(pos, is_even)]\n    \n    return form_subarrays(0, True)\n```\n\nCan we do better? Yes! In order to recognize how, we first need to convert top-down to bottom up:\n```python3\n# TC: O(n)\n# SC: O(n)\ndef maximumTotalCost(nums: List[int]) -> int:\n    n = len(nums)\n    # dp[i][0] stores the best score up to i when the last element is at an even position\n    # dp[i][1] stores the best score up to i when the last element is at an odd position\n    dp = [[0] * 2 for _ in range(n + 1)]\n    \n    for pos in range(n - 1, -1, -1):\n        dp[pos][0] = max(nums[pos] + dp[pos + 1][1], nums[pos] + dp[pos + 1][0])\n        dp[pos][1] = max(-nums[pos] + dp[pos + 1][0], nums[pos] + dp[pos + 1][1])\n    \n    return dp[0][0]\n```\n\nThe final thing to realize is that we only use the last 2 rows of the DP table. Therefore, we can make the solution O(1) space by replacing dp[pos+1] with \n# Solution\n```python3\ndef maximumTotalCost(self, nums: List[int]) -> int:\n    n = len(nums)\n    \n    # Initialize variables to store the current and previous states\n    cur = [0, 0]\n    prev = [0, 0]\n    \n    # Iterate from the end of the array to the beginning\n    for pos in range(n - 1, -1, -1):\n        # Compute the current states based on the previous states\n        prev[0] = max(nums[pos] + cur[1], nums[pos] + cur[0])\n        prev[1] = max(-nums[pos] + cur[0], nums[pos] + cur[1])\n        \n        # Update the current states to the previous states\n        cur[0], cur[1] = prev[0], prev[1]\n    \n    # The result is the maximum cost starting from the beginning with an even position\n    return cur[0]\n```\n\n# Complexity\n\n* Time Complexity: $O(n)$\n* Space Complexity: $O(1)$\n\n![image.png](https://assets.leetcode.com/users/images/aaa0ac85-0d29-4850-9b7f-46dafd317cf4_1719116231.6429458.png)\n\n
['Python3']