主題
題目連結：
題目意譯：
一個扭動序列（Wiggle Sequence）為一序列，其中連續數字之差值嚴格地於正負之間交錯。第一個差值（如果存在的話）可以為正或為負。一個只有一個元素的序列以及一個有兩個相異元素的序列必為扭動序列。
例如， [1, 7, 4, 9, 2, 5] 為一個扭動序列，因為其各個差值 (6, -3, 5, -7, 3) 於正負值之間交錯。
而相反地，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 則不是扭動序列。前者不符合是因為前兩個差值為正，而後者不符合是因為最後一個差值為零。
一個子序列可以藉由從原始序列中刪除若干個（可以為零）元素並使剩餘元素保持相對位置而得到。
給定一整數陣列 nums，回傳 nums 中最長的扭動子序列之長度。
限制：
1 ≦ nums.length ≦ 1000
0 ≦ nums[i] ≦ 1000
進階：你可以在 O(n) 的時間複雜度內解決嗎？
範例測資：
範例 1：
輸入： nums = [1,7,4,9,2,5]
輸出： 6
解釋： 整個序列為一個扭動序列，其差值為 (6, -3, 5, -7, 3)。
範例 2：
輸入： nums = [1,17,5,10,13,15,10,5,16,8]
輸出： 7
解釋： 有若干個子序列可以達到這個長度。
其中之一為 [1, 17, 10, 13, 10, 16, 8]，其差值為 (16, -7, 3, -3, 6, -8)。
範例 3：
輸入： nums = [1,2,3,4,5,6,7,8,9]
輸出： 2
解題思維：
（令 n = nums.length）
我們定義最後一個差值為正的扭動序列為「UP」，例如 [1, 7, 4, 9, 2, 5]；而最後一個差值為負者為「DOWN」，例如 [1, 7, 4, 9, 2]。
接著定義兩個陣列 U 和 D，其中 U[i] 代表以 nums[0] ～ nums[i] 所組成且為「UP」的最長扭動序列之長度、而 D[i] 代表以 nums[0] ～ nums[i] 所組成且為「DOWN」的最長扭動序列之長度。
可以看到一開始為 U[0] = D[0] = 1，因為只有一種扭動序列是以 nums[0] 組成。而遞迴式如下（對於 i > 0）：
如果 nums[i - 1] < nums[i]，代表我們可以延伸「UP」，因此
U[i] = D[i - 1] + 1、
D[i] = D[i - 1]
如果 nums[i - 1] > nums[i]，代表我們可以延伸「DOWN」，因此
D[i] = U[i - 1] + 1、
U[i] = U[i - 1]
因此我們從 i = 1 開始算到 nums 的結尾，此時可以看到 max(U[n - 1], D[n - 1]) 即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
