主題
題目連結(jié)：
題目意譯：
一個(gè)索引值從 0 開始的陣列之交錯(cuò)和定義為偶數(shù)索引值的元素總和減去奇數(shù)索引值的元素總和。
例如，[4,2,5,3] 的交錯(cuò)和為 (4 + 5) - (2 + 3) = 4。
給定一陣列 nums，回傳任意 nums 子序列中交錯(cuò)和之最大值（子序列經(jīng)過重新編排索引值）。
一個(gè)陣列的一子序列為一個(gè)新陣列，其藉由刪除原陣列中若干個(gè)（可能沒有）且不改變剩餘元素的相對(duì)順序下產(chǎn)生。例如，[2,7,4] 為 [4,2,3,7,2,1,4] 的一個(gè)子序列（劃有底線之元素），而 [2,4,2] 則不是。
限制：
1 ≦ nums.length ≦ 10 ^ 5
1 ≦ nums[i] ≦ 10 ^ 5
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [4,2,5,3]
輸出： 7
解釋： 最佳選擇為子序列 [4,2,5] 其交錯(cuò)和為 (4 + 5) - 2 = 7。
範(fàn)例 2：
輸入： nums = [5,6,7,8]
輸出： 8
解釋： 最佳選擇為子序列 [8] 其交錯(cuò)和為 8。
範(fàn)例 3：
輸入： nums = [6,2,1,2,4,5]
輸出： 10
解釋： 最佳選擇為子序列 [6,1,5] 其交錯(cuò)和為 (6 + 5) - 1 = 10。
解題思維：
（注意，本題的索引值皆為從 0 開始）
定義一個(gè)二維陣列 D，其中 D[i][j] 代表以從 nums[0] ～ nums[i] 所能產(chǎn)生的最大值且下一個(gè)數(shù)將是位於子序列的 j = 0（偶數(shù)索引值）或是 j = 1（奇數(shù)索引值）。
而我們可以看到
D[0][0] = nums[0] 、 D[0][1] = 0；
D[i][0] = max(D[i-1][0], D[i-1][1] + nums[i], nums[i])；
D[i][1] = max(D[i-1][1], D[i-1][0] - nums[i])。
其中 D[i][0] 是因?yàn)楝F(xiàn)在是 nums[0] ～ nums[i]，你最大的子序列要嘛來(lái)自 nums[0] ～ nums[i-1] 的解（D[i-1][0]）、要嘛就來(lái)自 nums[0] ～ nums[i-1] 的解附加進(jìn) nums[i]（D[i-1][1] + nums[i]），再不然就是來(lái)自於自己本身（nums[i]）；而 D[i][1] 也是類似的原理。
因此此時(shí)我們可以從 D[0][0] = nums[0] 、 D[0][1] = 0 一路往後推。而所求即是 D[nums.length - 1][0] 、 D[nums.length - 1][1] 的最大值。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
