天天看點

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

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

​ 中的最大子數組和」。

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

子問題定義的嘗試

很不幸,這麼定義子問題是行不通的。因為這麼定義的話,我們無法寫出子問題的遞推關系!

我們用一個實際的例子 ​

​[-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 并不相鄰。它們不能拼成一個連續的子數組!

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

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

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

正确的子問題定義

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

子問題 表示「​

​nums[0..k)​

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

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

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

子問題的新版定義

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

  • 這時候求的是​

    ​[-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)​

​ 中,以最後一個元素結尾的最長公共子數組」。

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

最長公共子數組問題的子問題定義

注意,這裡的以最後一個元素結尾指的是公共子數組既要包含 ​

​s[0..i)​

​​ 的最後一個元素,也要包含 ​

​t[0..j)​

​ 的最後一個元素。

換句話說,就是從後往前看 ​

​s[0..i)​

​​ 和 ​

​t[0..j)​

​ 的最後有幾個元素是相同的。

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

從後往前比較相同元素

那麼子問題的遞推關系如何定義呢?很簡單,我們還是隻需要看 ​

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

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

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