主題
題目連結：
題目意譯：
你被給定一個 m × n 整數矩陣 points（索引值從 0 開始）。起始分數為 0 分，你想要最大化你從矩陣中的得分。
為了獲得分數，你必須在每一列中挑一個數字。選擇位於座標 (r, c) 的格子將會增加 points[r][c] 點分數到你的分數值裡。
不過，你將會失去分數如果你挑了一個與前一列挑的格子太遠的格子。對於每兩列相鄰列 r 和 r + 1（其中 0 ≦ r < m - 1），挑選位於 (r, c1) 和 (r + 1, c2) 的格子將會從你的分數值減去 abs(c1 - c2)。
回傳你能得到的最大分數值。
abs(x) 定義為：
x 對於 x ≧ 0。
-x 對於 x < 0。
限制：
m == points.length
n == points[r].length
1 ≦ m 、 n ≦ 10 ^ 5
1 ≦ m × n ≦ 10 ^ 5
0 ≦ points[r][c] ≦ 10 ^ 5
範例測資：
範例 1：
輸入： points = [[1,2,3],[1,5,1],[3,1,1]]
輸出： 9
解釋：
藍色格子代表著最佳應挑的格子，其有著座標 (0, 2) 、 (1, 1) 和 (2, 0)。
你獲得了 3 + 5 + 3 = 11 點分數。
但是，你必須從你的分數裡減去 abs(2 - 1) + abs(1 - 0) = 2 點。
你的最終分數為 11 - 2 = 9。
範例 2：
輸入： points = [[1,5],[2,3],[4,2]]
輸出： 11
解釋：
藍色格子代表著最佳應挑的格子，其有著座標 (0, 1) 、 (1, 1) 和 (2, 0)。
你獲得了 5 + 3 + 4 = 12 點分數。
但是，你必須從你的分數裡減去 abs(1 - 1) + abs(1 - 0) = 1 點。
你的最終分數為 12 - 1 = 11。
解題思維：
我們定義一個二維陣列 D，其中 D[i][j] 代表著挑選第 i 列第 j 行的格子最大可以獲得的分數。
可以看到 D[0][j] = points[0][j]（因為第 0 列沒有前一列）。而 D[i][j] 為
max(D[i-1][0] - abs(j-0), D[i-1][1] - abs(j-1), ……) + points[i][j]
因此 D[i][j] 的最大值要嘛來自右側、要嘛來自左側，要不然就是他的正上方。而如果直接這麼做，每個位置都要掃過一次前一列的所有值。這樣下來時間複雜度將會是 O(m × n ^ 2)。
但是我們可以看到左與右這兩個方向是獨立彼此不互相影響的。畢竟前一列的最大值已經求出來了，不會再有所更動。
所以我們可以先從左到右掃過一次，再從右至左掃過一次。而當方向單一時，我們可以很容易地知道對於 (i, j) 的最大值貢獻者為何。
假設我們現在是由左至右，因此 (i, j) 目前的最大值只會來自於 (i - 1, 0) 、 (i - 1, 1) 、 …… 、 (i - 1, j)。而這個範圍之內的最大分數貢獻者可以藉由 (i, j - 1) 的最大值減 1（因為我們多往右了一格，所以要多減 1）以及當前的 D[i - 1][j] 比較得來。
因此一開始我們宣告一變數 M = 0。然後掃過第 i 列所有位置 j。我們先更新 M 為 max(M, D[i-1][j])，因此 D[i][j] 目前的值將會是 M + points[i][j]。之後我們將 M 減去 1（代表往右移動了一格）。
掃完之後便可以知道從左到右的最大值。然後再做一次從右到左（類似上面的過程），便可以正確地得知每個位置的最大分數值。
而最後掃過一次 D[m-1][0] 、 D[m-1][1] 等等從中取最大值，即是我們可以從整個矩陣中得到的最大分數值。
但是實際上我們會遇到一個小問題。例如二維陣列 D 有極大量的空間會被浪費，因為每一次求最大值我們只會用到兩列的空間，而再先前的最大值資訊已經無用武之地。因此我們可以改用兩個長度為 n 的陣列，然後交替地使用這兩個陣列來求得最大值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
