<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>
'''
題目的意思是
從它原本提供的list中
看要挑出幾個數字(這些數字的相對先後順序不會改變)
然後單數位置的數字總和會去減掉雙數位置的數字總和
問說怎樣挑才能得到最大

一開始想到的是
在還沒有挑出任何數字前(也就是還沒有第一個單數前)
要盡量先找比較大的數
當挑了一個單數之後，就變成要盡量挑小的數字
只要能夠維持大->小->大->小的順序
對於整體的總和就是正面影響

所以像題目給的例題二
[5,6,7,8]
它整個list是從小到大
不管怎麼挑，沒辦法達成理想的大小大小
所以就找一個最後一個8，來當單數，當最終答案

感覺可以用stack來解
當要找大的的時候
如果挑到的數，比stack上的當下還要大，就可以push
相反的
如果挑的的數，比stack上還要小，就去Pop
因為可以取代上一個小數，讓前面那一趴的大-小，所得到的結果更好
(因為要找大的，表示前面已經有一組大小先存在了，才有可能要找大的)

當要找小的就反過來

然後如果最後是找小的(也就是要減的)
可以再pop掉，省一次最後要減的數

阿等於的話怎辦?
如果目前要找大的
那遇到相等的數，就先取
也許後面會遇到更小的數
那也是好的

如果目前是要找小的
表示一胚都還沒有湊齊
如果一樣 x-x
雖然對整體的結果沒有幫助
但如果後面是一個比較大的
那為了這個大數，這個相等的就可以拿
i.e
5 5 8 =>整體+8

那如果是這樣
5 5 2
那不如挑後面那個2當小數

所以只要遇到相等的，都先拿...吧?
=>結果真的過了ㄏㄏ

class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        st = [nums[0]] #題目有提到一開始nums不會為空，所以一開始就先初始化進去
        findBig = False #所以代表大的已經有先拿了，現在要開始找小的
        for num in nums:
            if findBig:
                if st[-1] <= num:
                    findBig = not (findBig)
                else:
                    st.pop()
            else: #findSmall
                if st[-1] >= num:
                    findBig = not (findBig)
                else:
                    st.pop()
            st.append(num)
            
        if st and findBig:
            st.pop()
        result = 0
        for i in range(len(st)):
            if i % 2 == 0:
                result += st[i]
            else:
                result -= st[i]
        return result
==================================
之後有看到用Kadane 演算法解的方式
是可以用來解最大子數列問題的方法

主要的精神在於
如果今天一串數列
一直累加到了某一個位置i
       i i+1
XXXXXXXX  y

那他如果要把下一個位置i+1 的數字也加進來
最大值有可能是多少
只會有兩種可能
要馬就是 目前累加到i 的數 =>(因為i+1這個位置的數可能是負的，把它吃進來只會讓數變小)
不然的話就是 把i+1的數也包進來 =>(因為如果i+1是正數的話，那多累加它進來就會讓數變大)

但是因為這題要 +或- 會隨著位置而改變
如果一個數
它在雙數位 0 2 4 就是要被加
他在單數位 1 3 5 就是要被減

如果目前某個位置 他現在是雙數
那它等等就會變單數
 0 1 2 3 4 5
[6,2,1,2,4,5]

原本是 先看位置0 
如果把它當成+6 或-6
哪一個比較好 =>+6比較好
那如果把它當成+6了
evenTotal => 6
oddTotal => 0

那再看下一個 2
要把前面位置當成+，還是把這個位置當成+?
如果要把這個位置當成+的話，意思就是
要加上把前面當成-的結果
然後去跟
把前面位置當成加的結果比
看哪一個比較好
evenTotal = max(preEvenTotal, preOddTotal+2)

以此類推下去
幹其實我也是看不懂到底怎麼想出這樣的怪招
'''
class Solution:
    def maxAlternatingSum(self, nums: List[int]) -> int:
        addTotal = 0
        minusTotal = 0
        result = 0
        for i in range(len(nums)):
            prevAddTotal = addTotal
            prevMinusTotal = minusTotal

            addTotal = max(prevAddTotal, minusTotal+nums[i])
            minusTotal = max(prevMinusTotal, addTotal-nums[i])

            result = max(addTotal, minusTotal, result)
        return result



        
915