主題
題目連結(jié)：
題目意譯：
你被給定一個(gè)索引值從 0 開(kāi)始數(shù)的整數(shù)陣列 nums。
回傳所有索引值三元組 (i, j, k) 的數(shù)值最大值，其中每一個(gè)三元組滿足 i < j < k。如果所有索引值三元組的數(shù)值都是負(fù)的，則回傳 0。
一個(gè)索引值三元組 (i, j, k) 的數(shù)值等於 (nums[i] - nums[j]) × nums[k]。
限制：
3 ≦ nums.length ≦ 100
1 ≦ nums[i] ≦ 10 ^ 6
範(fàn)例測(cè)資：
範(fàn)例 1：
輸入： nums = [12,6,1,2,7]
輸出： 77
解釋： 索引值三元組 (0, 2, 4) 的數(shù)值為 (nums[0] - nums[2]) × nums[4] = 77。
可以證明沒(méi)有其他索引值三元組有著大於 77 的數(shù)值。
範(fàn)例 2：
輸入： nums = [1,10,3,4,19]
輸出： 133
解釋： 索引值三元組 (1, 2, 4) 的數(shù)值為 (nums[1] - nums[2]) × nums[4] = 133。
可以證明沒(méi)有其他索引值三元組有著大於 133 的數(shù)值。
範(fàn)例 3：
輸入： nums = [1,2,3]
輸出： 0
解釋： 唯一一個(gè)索引值三元組 (0, 1, 2) 有著負(fù)的數(shù)值 (nums[0] - nums[1]) × nums[2] = -3。因此答案為 0。
解題思維：
（令 n = nums.length）
由於 n 最大也才 100，因此直接用三層迴圈窮舉 (i, j, k) 並計(jì)算數(shù)值取最大值即可。時(shí)間複雜度很明顯地是 O(n ^ 3)。
不過(guò)有鑑於「下一題」（Leetcode 2874，明天的題目）是本題的強(qiáng)化版（n 最大值變大到 10 ^ 5），因此還是講解一下線性的解法：
令 F(i, j, k) = (nums[i] - nums[j]) × nums[k] 且 D(i, j) = nums[i] - nums[j]。以下部份預(yù)設(shè) i < j < k，也就是說(shuō)不會(huì)出現(xiàn) D(5, 2) 這種東西。
首先觀察一下 F(i, j, k)。如果現(xiàn)在我們固定索引值 k 不變，要最大化 F(i, j, k) 之值即是最大化 D(i, j) 之值。
而這代表著，如果現(xiàn)在隨便取一個(gè)元素 nums[x] 作為 F(i, j, k) 中的 nums[k]，則從 nums[0] ~ nums[x - 1] 找出最大的 D(i, j) 之值便可以最大化 F(i, j, x)。
而我們可以看到 nums[x + 1] 的最大 D(i, j) 之值可以從 nums[x] 繼承之後，再加上從 nums[0] ~ nums[x - 1] 任挑數(shù)字與 nums[x] 相減（即 D(i, x)）的最大值，前者與後者取最大值即可得到 nums[x + 1] 的最大 D(i, j)。
此時(shí)如果我們是每一次從 nums[x] 移動(dòng)到 nums[x + 1] 時(shí)繼承 nums[x] 的最大 D(i, j) 值再窮舉 D(i, x) 之值比大小，則時(shí)間複雜度是 O(n ^ 2)。
不過(guò)我們可以對(duì) D(i, j) 做跟 F(i, j, k) 類似的事情——固定 nums[j]，可以得到最大化 D(i, j) 等價(jià)於最大化 nums[i] 值。
也就是說(shuō)對(duì)於任意一個(gè)元素 nums[x]，D(i, x) 的最大值其實(shí)就取決於 nums[0] ~ nums[x - 1] 中的最大值。
而從 D(i, x - 1) 變化到 D(i, x) 可以看到前者是求 nums[0] ~ nums[x - 2] 中的最大值、後者是 nums[0] ~ nums[x - 1] 中的最大值。兩者只差在 nums[x - 1]。
所以 D(i, x) 可以直接繼承從 D(i, x - 1) 得到的最大值再與 nums[x - 1] 判斷大小即可得到 nums[0] ~ nums[x - 1] 中的最大值。
也因此從 nums[x] 移動(dòng)到 nums[x + 1] 時(shí)，我們只需要 O(1) 時(shí)間便可以得到 D(i, x) 的最大值。進(jìn)而在 O(1) 時(shí)間內(nèi)計(jì)算出 F(i, j, x + 1) 的最大值。
因故最後的時(shí)間複雜度降為 O(n)。
此次分享到此為止，如有任何更加簡(jiǎn)潔的想法或是有說(shuō)明不清楚之地方，也煩請(qǐng)各位大大撥冗討論。
