<p>The <strong>alternating sum</strong> of a <strong>0-indexed</strong> array is defined as the <strong>sum</strong> of the elements at <strong>even</strong> indices <strong>minus</strong> the <strong>sum</strong> of the elements at <strong>odd</strong> indices.</p>

<ul>
	<li>For example, the alternating sum of <code>[4,2,5,3]</code> is <code>(4 + 5) - (2 + 3) = 4</code>.</li>
</ul>

<p>Given an array <code>nums</code>, return <em>the <strong>maximum alternating sum</strong> of any subsequence of </em><code>nums</code><em> (after <strong>reindexing</strong> the elements of the subsequence)</em>.</p>

<ul>
</ul>

<p>A <strong>subsequence</strong> of an array is a new array generated from the original array by deleting some elements (possibly none) without changing the remaining elements&#39; relative order. For example, <code>[2,7,4]</code> is a subsequence of <code>[4,<u>2</u>,3,<u>7</u>,2,1,<u>4</u>]</code> (the underlined elements), while <code>[2,4,2]</code> is not.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [<u>4</u>,<u>2</u>,<u>5</u>,3]
<strong>Output:</strong> 7
<strong>Explanation:</strong> It is optimal to choose the subsequence [4,2,5] with alternating sum (4 + 5) - 2 = 7.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [5,6,7,<u>8</u>]
<strong>Output:</strong> 8
<strong>Explanation:</strong> It is optimal to choose the subsequence [8] with alternating sum 8.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [<u>6</u>,2,<u>1</u>,2,4,<u>5</u>]
<strong>Output:</strong> 10
<strong>Explanation:</strong> It is optimal to choose the subsequence [6,1,5] with alternating sum (6 + 5) - 1 = 10.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        '''
        does that make it the best we can have? no it doesn't guarantee it
        do we include it or do we not
        what is the max alternating subsequence when we use these elements?
        what is the decision we can make
        '''
        # let's try making a recursive solution
        # now let's try memoizing -> we need one to keep track of index and then one to keep track of state

        dp = [[0 for _ in range(2)] for _ in range(len(nums))]
        # dp[i][0] = add, dp[i][1] = subtract
        # let's try bottom up now
        retval = 0
        for i in range(len(nums)):
            for j in range(2):
                if j == 0:
                    dp[i][j] = max(nums[i] + dp[i-1][1], dp[i-1][0])
                else:
                    dp[i][j] = max(dp[i-1][1], dp[i-1][0] - nums[i])
                retval = max(retval, dp[i][j])
        
        return retval

        # def dfs(idx, state):
        #     if idx == len(nums):
        #         return 0
            
        #     if (idx, state) in dp:
        #         return dp[(idx, state)]
            
        #     cur = nums[idx] * state
        #     if state == -1:
        #         # this means negative
        #         dp[(idx, state)] = max(dfs(idx +1, -1), cur + dfs(idx + 1, 1))
        #     else:
        #         dp[(idx, state)] = max(cur + dfs(idx + 1, -1), dfs(idx + 1, 1)) 

        #     return dp[(idx, state)]

        # return dfs(0, 1)
1316