LeetCode 例題精講 | 16 最大子數組和：子數組類問題的動态規劃技巧

本期例題：

• 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；
• 即​

  ​[-1, 2]​

  ​ 的最大和子數組為 ​

  ​[2]​

  ​，和為 2；
• 即​

  ​[-1, 2, 3]​

  ​ 的最大和子數組為 ​

  ​[2, 3]​

  ​，和為 5；
• 即​

  ​[-1, 2, 3, -2]​

  ​ 的最大和子數組為 ​

  ​[2, 3]​

  ​，和為 5；
• 即​

  ​[-1, 2, 3, -2, 4]​

  ​ 的最大和子數組為 ​

  ​[2, 3, -2, 4]​

  ​，和為 7；
• 即​

  ​[-1, 2, 3, -2, 4, 1]​

  ​ 的最大和子數組為 ​

  ​[2, 3, -2, 4, 1]​

  ​，和為 8。

在依次計算子問題的過程中， 到

求出 ​

​[-1, 2, 3, -2]​

​​ 的最大和子數組和為 ​

​[2, 3]​

​，位于數組的中部。

求 的時候，我們加入了一個新元素 4。自然地，我們想知道這個新元素能不能與

求出的最優解相結合，得到

的最優解 ​

​[2, 3]​

​，和新元素 4 并不相鄰。它們不能拼成一個連續的子數組！

嘗試構造子問題的遞推關系

可見，問題出在「子數組」的限制上。子數組要求元素是連續的，那麼，前一個子問題的最優解，可能在後一個子問題中用不上。子問題的遞推鍊條就斷開了。

正确的子問題定義

那麼，怎麼解決這個子問題「續不上」的問題呢？答案是修改子問題的定義，加一個限制條件：

子問題 表示「​

​nums[0..k)​

​ 中，以最後一個元素結尾的最大子數組和」。

既然子數組拼接不起來，那麼我們就限制子問題計算的子數組隻能位于數組尾部。這樣得到的最大和子數組，就一定可以跟下一個元素拼接起來了。

子問題的新版定義

我們來看看這時候的子問題是怎麼計算的：

• 這時候求的是​

  ​[-1, 2, 3, - 2]​

  ​ 中位于數組尾部的最大子數組和，結果是 ​

  ​[2, 3, -2]​

  ​，和為 3。
• 計算 的時候，直接把新元素 4 跟前面的最優解​

  ​[2, 3, -2]​

  ​ 拼接起來，得到最大和子數組是 ​

  ​[2, 3, -2, 4]​

  ​，和為 7。

子問題的遞推關系

正确定義了子問題，就可以寫出子問題的遞推關系了。我們用 表示元素 ​

​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）

都是很典型的子數組類題目，可以試着練習一下。

​

歡迎關注我的公衆号“五分鐘學算法”，如果喜歡，麻煩點一下