本期例題：
- LeetCode 53. Maximum Subarray Sum 最大子數組和（Easy）
- LeetCode 718. Maximum Length of Repeated Subarray 最長公共子數組（Medium）
在前面的文章中，我們分别講解了一維和二維動态規劃問題的解題步驟與基本思路。不過，僅僅掌握基本步驟是不夠的。要想熟練做出動态規劃題目，還要掌握足夠的解題技巧。
接下來的文章中，我會講解動态規劃問題中針對不同類型問題的小技巧。今天要講的是關于「子數組」類題目的常見技巧。
在講具體問題之前，我們要明确一下「子數組」和「子序列」的概念。
- 子序列 (subsequence) 可以是不連續的。例如 "ACD" 是 "ABCDE" 的子序列；
- 子數組 (subarray)、子串 (substring) 必須是連續的。例如 "BCD" 是 "ABCDE" 的子數組/子串。
我們前面的例題中講過的最長公共子序列問題，關注的是「子序列」，而今天的文章我們要關注的都是「子數組」，請牢記這一點。
這篇文章的内容包括：
- 子數組類問題的動态規劃技巧
- 「最大子數組和」問題的解法
- 「最長公共子數組」問題的解法
最大子數組和
LeetCode 53. Maximum Subarray Sum 最大子數組和（Easy）
給定一個整數數組 nums
，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。
子問題定義的錯誤嘗試
拿到這道「最大子數組和」問題，如果直接把動态規劃的解題四步驟往上套，那麼你可能首先會想到這麼定義子問題：
子問題 表示「
nums[0..k)
中的最大子數組和」。
子問題定義的嘗試
很不幸，這麼定義子問題是行不通的。因為這麼定義的話，我們無法寫出子問題的遞推關系！
我們用一個實際的例子
[-1, 2, 3, -2, 4, 1]
，看看每個子問題計算的結果：
- 即
[-1]
[-1]
- 即
[-1, 2]
[2]
- 即
[-1, 2, 3]
[2, 3]
- 即
[-1, 2, 3, -2]
[2, 3]
- 即
[-1, 2, 3, -2, 4]
[2, 3, -2, 4]
- 即
[-1, 2, 3, -2, 4, 1]
[2, 3, -2, 4, 1]
在依次計算子問題的過程中， 到
求出
[-1, 2, 3, -2]
的最大和子數組和為
[2, 3]
，位于數組的中部。
求 的時候，我們加入了一個新元素 4。自然地，我們想知道這個新元素能不能與
求出的最優解相結合，得到
的最優解
[2, 3]
，和新元素 4 并不相鄰。它們不能拼成一個連續的子數組！
嘗試構造子問題的遞推關系
可見，問題出在「子數組」的限制上。子數組要求元素是連續的，那麼，前一個子問題的最優解，可能在後一個子問題中用不上。子問題的遞推鍊條就斷開了。
正确的子問題定義
那麼，怎麼解決這個子問題「續不上」的問題呢？答案是修改子問題的定義，加一個限制條件：
子問題 表示「
nums[0..k)
中，以最後一個元素結尾的最大子數組和」。
既然子數組拼接不起來，那麼我們就限制子問題計算的子數組隻能位于數組尾部。這樣得到的最大和子數組，就一定可以跟下一個元素拼接起來了。
子問題的新版定義
我們來看看這時候的子問題是怎麼計算的：
- 這時候求的是
[-1, 2, 3, - 2]
[2, 3, -2]
- 計算 的時候，直接把新元素 4 跟前面的最優解
[2, 3, -2]
[2, 3, -2, 4]
子問題的遞推關系
正确定義了子問題，就可以寫出子問題的遞推關系了。我們用 表示元素
nums[i]
，寫出的子問題遞推公式為：
這個遞推公式的含義是，計算
nums[0..k)
的最大子數組和時，要麼是把新元素
nums[k-1]
加入前一個子問題的結果（即 的含義），要麼是隻使用元素
nums[k-1]
，選擇其中結果較大的一個方案。
這個遞推公式可以繼續化簡為：
這樣，我們就可以寫出題解代碼了：
public int maxSubArray(int[] nums) {
// 子問題：
// f(k) = nums[0..k) 中以 nums[k-1] 結尾的最大子數組和
// 原問題 = max{ f(k) }, 0 <= k <= N
// f(0) = 0
// f(k) = max{ f(k-1), 0 } + nums[k-1]
int N = nums.length;
int[] dp = new int[N+1];
dp[0] = 0;
int res = Integer.MIN_VALUE;
for (int k = 1; k <= N; k++) {
dp[k] = Math.max(dp[k-1], 0) + nums[k-1];
res = Math.max(res, dp[k]);
}
return res;
} 需要注意的是，我們最後不能直接傳回最後一個子問題 的結果。因為我們子問題的定義變了，
限于文章篇幅，我們這裡就不讨論這道題的空間優化方法以及其他解法了。以後會專門寫一篇文章介紹這道題的不同解法。
最長公共子數組
了解了「最大子數組和」問題的解法，我們再來看一道類似思路的二維動态規劃問題：最長公共子數組。
LeetCode 718. Maximum Length of Repeated Subarray 最長公共子數組（Medium）
給兩個整數數組 和 s
t
，傳回兩個數組中公共的、長度最長的子數組的長度。例如：
輸入:s: [1, 2, 3, 2, 1, 5]
t: [6，3, 2, 1, 4, 7]
輸出: 3
解釋:
長度最長的公共子數組是 [3, 2, 1]。
「最長公共子數組」問題其實和「最長公共子序列」問題相似，隻是把題目中的「子序列」換成了「子數組」。如果你對「最長公共子序列」問題不是很熟悉，可以回顧之前的文章：
LeetCode 例題精講 | 15 最長公共子序列：二維動态規劃的解法
在「最長公共子序列」問題中，我們是這樣定義子問題的：
子問題 表示「
s[0..i)
和
t[0..j)
的最長公共子序列」。
然而，當問題變成「子數組」以後，子數組的性質導緻了原先的子問題遞推關系不成立了，我們需要重新定義子問題。我們參考上一道例題的方法，給子數組加上一個位于數組尾部的限制，将子問題定義成這樣：
子問題 表示「
s[0..i)
和
t[0..j)
中，以最後一個元素結尾的最長公共子數組」。
最長公共子數組問題的子問題定義
注意，這裡的以最後一個元素結尾指的是公共子數組既要包含
s[0..i)
的最後一個元素，也要包含
t[0..j)
的最後一個元素。
換句話說，就是從後往前看
s[0..i)
和
t[0..j)
的最後有幾個元素是相同的。
從後往前比較相同元素
那麼子問題的遞推關系如何定義呢？很簡單，我們還是隻需要看
s[0..i)
和
t[0..j)
的最後一個元素：
s[i-1]
和
t[j-1]
。
- 如果
s[i-1] == t[j-1]
s[0..i-1)
t[0..j-1)
- 如果
s[i-1] != t[j-1]
這樣我們就得到了子問題的遞推公式：
那麼原問題如何由子問題表示呢？是這樣的：
這樣，我們就可以寫出題解代碼了：
public int findLength(int[] s, int[] t) {
// 子問題：
// f(i, j) = s[0..i) 和 t[0..j) 中以 s[i-1] 和 t[j-1] 結尾的最長公共子數組
// 原問題 = max{ f(i, j) }, 0 <= i <= m, 0 <= j <= n
// f(0, *) = 0
// f(*, 0) = 0
// f(i, j) = max:
// f(i-1, j-1) + 1, if s[i-1] == t[j-1]
// 0 , if s[i-1] != t[j-1]
int m = s.length;
int n = t.length;
int[][] dp = new int[m+1][n+1];
int res = 0;
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
} else {
if (s[i-1] == t[j-1]) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = 0;
}
}
res = Math.max(res, dp[i][j]);
}
}
return res;
} 總結
從以上兩個例題中，我們可以看出「子數組」類問題的解題套路。我們可以在定義子問題的時候加上位于數組尾部的限制條件。這樣才可以正常地推導出子問題的遞推關系。
本文講解的第二個例題「最長公共子數組」和「最長公共子序列」僅僅一個概念上的差距，子問題的定義和遞推關系就有很多不同。建議大家把這兩道題對照着來做，可以很容易地體會到「子數組」和「子序列」問題的不同之處。這裡放上兩道題的題号：
- LeetCode 1143. Longest Common Subsequence 最長公共子序列（Medium）
- LeetCode 718. Maximum Length of Repeated Subarray 最長公共子數組（Medium）
除了例題之外，LeetCode 上還有一些「子數組」類的題目：
- LeetCode 152. Maximum Subarray Product 最大乘積子數組（Medium）
- LeetCode 978. Longest Turbulent Subarray 最長波形子數組（Medium）
都是很典型的子數組類題目，可以試着練習一下。
歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下