🔗 🟡 53. Maximum Subarray

題意

給定一個整數陣列 nums，找出具有最大和的非空子陣列，並返回其和。

子陣列是陣列中的連續部分。

Follow-up

如果你已經實現 O(n)O(n) 的解法，嘗試使用更為精妙的 分治法(Divide and Conquer) 求解。

約束條件

  • 1≤nums.length≤1051 \leq \text{nums.length} \leq 10^5
  • −104≤nums[i]≤104-10^4 \leq \text{nums[i]} \leq 10^4

思路

方法一：前綴和(Prefix Sum) + 枚舉右維護左

首先從暴力作法出發，即枚舉所有可能的子陣列，計算其和，並更新最大和。但所有可能的子陣列有 O(n2)O(n^2) 個，且計算每個子陣列的和需要 O(n)O(n) 時間，故總時間複雜度為 O(n3)O(n^3)，顯然不夠高效。

故我們可以考慮如何優化這個過程，而一段區間的和可以通過 前綴和(Prefix Sum) 來快速計算。令 s[i]s[i] 為前 ii 個元素的和，則區間 [l,r][l, r] 的和可以表示為 s[r]−s[l−1]s[r] - s[l-1]。這樣可以將計算子陣列和的時間複雜度從 O(n)O(n) 降到 O(1)O(1)，但 O(n2)O(n^2) 的時間複雜度仍然不夠高效。

而當固定右端點 rr 時，我們的目標是找到最大的 s[r]−s[l−1]s[r] - s[l-1]，這等同找到最小的 s[l−1]s[l-1]。故我們可以枚舉右端點、維護左端點，也就是一邊計算前綴和 s[r]s[r] 一邊維護最小的 s[l−1]s[l-1]，如此便可以在 O(n)O(n) 時間內求解。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 是陣列的長度。
  • 空間複雜度：O(1)O(1)。
1
2
3
4
5
6
7
8
9
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = float('-inf')
        s = mn = 0
        for x in nums:
            s += x
            ans = max(ans, s - mn)
            mn = min(mn, s)
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN, s = 0, mn = 0;
    for (int x : nums) {
      s += x;
      ans = max(ans, s - mn);
      mn = min(mn, s);
    }
    return ans;
  }
};

方法二：動態規劃(Dynamic Programming)

類似地，我們可以固定右端點，定義 f(i)f(i) 為以 nums[i]nums[i] 結尾的最大子陣列和。而在考慮第 ii 個元素時，我們有兩種選擇：

  1. 將當前元素 nums[i]nums[i] 和先前的子陣列相連，即與 nums[i−1]nums[i-1] 相連。而根據問題的定義，f(i−1)f(i-1) 代表以 nums[i−1]nums[i-1] 結尾的最大子陣列和，因此此時能獲得的最大子陣列和為 f(i−1)+nums[i]f(i-1) + nums[i]。
  2. 重新開始一個新的子陣列，即 nums[i]nums[i]。

因此可以得到狀態轉移方程為：

f(i)=max⁡(f(i−1)+nums[i],nums[i])f(i) = \max(f(i-1) + nums[i], nums[i])

邊界條件為 f(0)=nums[0]f(0) = nums[0]，或是定義 f(−1)=0f(-1) = 0。這裡使用後者，但為此需要偏移一個位置。

而根據問題的定義，所有以 nums[i]nums[i] 結尾的子陣列都有可能是答案，因此我們需要考慮所有可能的子陣列，最終答案為 max⁡0≤i<nf(i)\displaystyle\max_{0 \leq i < n} f(i)。

這個演算法即為 Kadane's Algorithm 。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 是陣列的長度。
  • 空間複雜度：O(n)O(n)，為陣列 ff 的空間。
1
2
3
4
5
6
7
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        f = [-float('inf')] * (n + 1)
        for i, x in enumerate(nums):
            f[i + 1] = max(f[i] + x, x)
        return max(f)
1
2
3
4
5
6
7
8
9
10
11
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> f(n + 1, -INT_MAX / 2);
    for (int i = 0; i < n; ++i) {
      f[i + 1] = max(f[i] + nums[i], nums[i]);
    }
    return *max_element(f.begin(), f.end());
  }
};

方法二優化：滾動陣列(Rolling Array)

在原本的方法二中，我們需要一個額外的陣列 ff 來存儲所有的 f(i)f(i) 值，但實際上，我們只需要考慮前一個狀態 f(i−1)f(i-1) 即可。因此，我們可以可以用 滾動 的方式優化空間複雜度，使用一個變數 ff 來記錄 f(i−1)f(i-1)。

但這樣我們會損失 f(i)f(i) 的資訊，因此我們需要動態地在更新 ff 的同時更新最大值 ansans。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 是陣列的長度。
  • 空間複雜度：O(1)O(1)。
1
2
3
4
5
6
7
8
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -float('inf')
        f = 0
        for x in nums:
            f = max(f + x, x)
            ans = max(ans, f)
        return ans
1
2
3
4
5
6
7
8
9
10
11
class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    int ans = INT_MIN, f = 0;
    for (int x : nums) {
      f = max(f + x, x);
      ans = max(ans, f);
    }
    return ans;
  }
};

方法三：分治法(Divide and Conquer)

方法三的 O(n)O(n) 解法遠超 Medium 題目難度，可以自行斟酌是否需要閱讀。

這裡是 Follow-up 的內容，我們需要使用分治法來解決這個問題。為此，我們可以將區間 [l,r][l, r] 分為兩半，對每一半分別求解最大子陣列和，然後再進行合併以計算整個數組的最大子陣列和。具體來說，對於任意一個區間 [l,r][l, r]，我們可以將其分為兩個子區間 [l,mid][l, mid] 和 [mid+1,r][mid+1, r]，其中 mid=⌊l+r2⌋mid = \lfloor \frac{l + r}{2} \rfloor。對這兩個子區間分別計算最大子陣列和，然後再結合這兩個結果來得到區間 [l,r][l, r] 的最大子陣列和。

但問題在於應如何合併兩個子陣列的結果。而區間 [l,r][l, r] 的最大子陣列和只可能會有以下 33 種情況：

  1. 出現在左半邊 [l,mid][l, mid]
  2. 出現在右半邊 [mid+1,r][mid+1, r]
  3. 跨越兩個子陣列 [l,mid]+[mid+1,r][l, mid] + [mid+1, r]

對於情況 11 和 22，我們可以遞迴地求解。而對於情況 33，我們需要考慮跨越兩個子陣列的情況。而跨越兩個子陣列就代表 midmid 和 mid+1mid+1 在此最大子陣列中間，故只需要考慮 以 mid 為右端點 和 以 mid+1 為左端點 的最大子陣列和，即可合併出跨越兩個子陣列的最大子陣列和。

雖然簡單的向左和向右延伸求解即可，但那會導致時間複雜度為 O(nlog⁡n)O(n \log n)，這裡我們使用 O(n)O(n) 的解法。

為此，我們可以維護區間 [l,r][l, r] 的以下 44 個性質：

  • 以 ll 為左端點的最大子陣列和 lSumlSum
  • 以 rr 為右端點的最大子陣列和 rSumrSum
  • 區間內最大子陣列和 mSummSum
  • 區間內所有元素和 tottot

而這 44 個性質可以都通過遞迴求解，並在合併時進行合併。為了方便說明，我們定義一個資料結構 Node 來存儲這 44 個性質。並令 lsls 和 rsrs 分別代表 [l,mid][l, mid] 和 [mid+1,r][mid+1, r] 的結果。

  • 在合併 lSumlSum 時，只需要考慮是否跨越兩個區間，若跨越則必包含 [l,mid][l, mid] 的所有元素，並根據定義，ls.tot+rs.lSumls.tot + rs.lSum 即為跨越兩個區間的 lSumlSum，因此 lSum=max⁡(ls.lSum,ls.tot+rs.lSum)lSum = \max(ls.lSum, ls.tot + rs.lSum)。
  • 同理，在合併 rSumrSum 時，只需要考慮是否跨越兩個區間，若跨越則必包含 [mid+1,r][mid+1, r] 的所有元素，並根據定義，rs.tot+ls.rSumrs.tot + ls.rSum 即為跨越兩個區間的 rSumrSum，因此 rSum=max⁡(rs.rSum,rs.tot+ls.rSum)rSum = \max(rs.rSum, rs.tot + ls.rSum)。
  • 根據上述說明，mSummSum 的合併方式為 max⁡(ls.mSum,rs.mSum,ls.rSum+rs.lSum)\max(ls.mSum, rs.mSum, ls.rSum + rs.lSum)。
  • 最後，tottot 的合併方式顯然為 ls.tot+rs.totls.tot + rs.tot。

如上所述，我們可以通過遞迴求解，並在合併時進行合併，最終得到區間 [l,r][l, r] 的最大子陣列和。

補充說明：線段樹思想

雖然 Divide and Conquer 的作法和前兩種方法的時間複雜度都是 O(n)O(n)，但由於使用了遞迴並需要維護 44 個性質，導致常數較大。

但這種方法的優勢在於可以利用分治法來任意的子區間 [l,r][l, r] 的問題。

既然我們可以合併兩個連續的區間，那麼利用 Divide and Conquer 建立的 O(n)O(n) 個區間（事實上，不會超過 4n4n 個），我們可以在 O(log⁡n)O(\log n) 的時間求出任意區間 [l,r][l, r] 內的最大子陣列和。

此外，若我們需要修改某個位置的元素，也只需要修改到 O(log⁡n)O(\log n) 個區間，故單點修改可以在 O(log⁡n)O(\log n) 的時間內完成。

因此在 O(n)O(n) 的初始化之後，可以在 O(log⁡n)O(\log n) 的時間做到區間查詢和單點修改，這種利用 Divide and Conquer 維護區間內的性質的方式，也就是 線段樹(Segment Tree) 的基本思想。

筆力有限，這裡只是引入基本概念，有興趣者可以自行閱讀相關文章：线段树从入门到急停。

複雜度分析

  • 時間複雜度：O(n)O(n)，其中 nn 是陣列的長度。
    • 令 T(n)T(n) 為遞迴求解的時間複雜度，則 T(n)=2T(n2)+O(1)T(n) = 2T(\frac{n}{2}) + O(1)，根據 主定理(Master Theorem)，得 T(n)=O(n)T(n) = O(n)。
  • 空間複雜度：O(log⁡n)O(\log n)，為遞迴所需的棧空間。
    • 若我們保存中間結果，則空間複雜度為 O(n)O(n)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Node:
    def __init__(self, lSum, rSum, mSum, tot):
        self.lSum = lSum
        self.rSum = rSum
        self.mSum = mSum
        self.tot = tot

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        def query(l, r):
            if l == r:
                return Node(nums[l], nums[l], nums[l], nums[l])
            mid = (l + r) >> 1
            ls = query(l, mid)
            rs = query(mid + 1, r)
            # Combine
            lSum = max(ls.lSum, ls.tot + rs.lSum)
            rSum = max(rs.rSum, rs.tot + ls.rSum)
            mSum = max(ls.mSum, rs.mSum, ls.rSum + rs.lSum)
            tot = ls.tot + rs.tot
            return Node(lSum, rSum, mSum, tot)

        return query(0, len(nums) - 1).mSum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct Node {
  int lSum, rSum, mSum, tot;
  Node(int lSum, int rSum, int mSum, int tot)
      : lSum(lSum), rSum(rSum), mSum(mSum), tot(tot) {}
};

class Solution {
 public:
  int maxSubArray(vector<int>& nums) {
    auto query = [&](auto&& query, int l, int r) -> Node {
      if (l == r) return Node(nums[l], nums[l], nums[l], nums[l]);
      int mid = (l + r) >> 1;
      auto ls = query(query, l, mid);
      auto rs = query(query, mid + 1, r);
      // Combine
      int lSum = max(ls.lSum, ls.tot + rs.lSum);
      int rSum = max(rs.rSum, rs.tot + ls.rSum);
      int mSum = max(max(ls.mSum, rs.mSum), ls.rSum + rs.lSum);
      int tot = ls.tot + rs.tot;
      return Node(lSum, rSum, mSum, tot);
    };
    return query(query, 0, nums.size() - 1).mSum;
  }
};

類題

動態規劃

分治法

參考資料

寫在最後

PROMPT

masterpiece, best quality, high quality, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, backlight, photo background,

1other, solo, no humans, Sylveon, Sylveon (Pokémon), Pokémon, blue eyes, full body, outdoors, sky, day, o, blue sky, grass, grassland, looking up,

A serene hand-drawn scene featuring Sylveon, a Pokémon with flowing ribbons, standing in a vibrant green meadow under a clear blue sky. Its eyes are blue, and its ears are a vibrant shade of pink, while its tail is a lighter shade of gray. The ribbons are gently swaying in the wind, and the art style is soft and painterly, emphasizing tranquility and freedom. Detailed grass in the foreground contrasts with the bright, open sky.

這題同樣是近期在考研群組回應過的題目，但 LeetCode 官方和大學課程中的分治法都使用 O(nlog⁡n)O(n \log n) 的解法，但更精妙的分治法應該是需要在同樣 O(n)O(n) 的時間複雜度內求解。

一開始寫這題的時候，也是使用 O(nlog⁡n)O(n \log n) 的分治解法，但後來在一次週賽寫不出線段樹題後，被大佬罵說是不是有真的弄懂這題，因此才開始研究這精妙的 O(n)O(n) 分治解法。

方法三應遠超 Medium 題目難度，可以自行斟酌是否需要閱讀。