53. 最大子序和 （動态規劃/分治）

文章目錄

• • • • 最大子序和問題
      • • 基礎解法
        • 利用特性
        • 動态規劃
        • 分治

最大子序和問題

給定一個整數數組 nums ，找到一個具有最大和的連續子數組（子數組最少包含一個元素），傳回其最大和。

示例 1：

輸入：nums = [-2,1,-3,4,-1,2,1,-5,4]

輸出：6

解釋：連續子數組 [4,-1,2,1] 的和最大，為 6 。

基礎解法

将容器所有的可能組合都進行求值得出其中最大值。

int maxSubArray(vector<int>& nums) {
	int size = nums.size();
	int value = 0;
	int result = nums[0]; // 将第一個值最為初始比較值
	for (int start = 0; start < size; start++)
	{
		value = 0;
		for(int j = start; j < size; j++)
		{
			value += nums[j];
			if(result < value)
			{
				result = value;
			}
		}
	}
	return result;
}
           

• 時間複雜度

  O(n^2)

• 空間複雜度

  O(1)

利用特性

對于該問題，則必有最大得組合開始和結尾得資料均為正數 ，不可能存在開始或結束值為負數求得最大值。

int maxSubArray(vector<int>& nums) {
	int res = nums[0];
    int sum = 0;
    for (int num : nums) {
        if (sum > 0)
            sum += num;
        else  // 值為負數，重新開始累計
            sum = num;
        res =  std::max(res, sum); // 求得最大值
    }
    return res;
}
           

• 時間複雜度

  O(n)

• 空間複雜度

  O(1)

動态規劃

實際上是把特性，提取出來理論。

假設數組nums的長度為N，則下标範圍為[0,N-1]

我們用 f(i) 代表以第 i 個數結尾的「連續子數組的最大和」，那麼很顯然我們要求的答案就是：

所有f(i)中最大的那一個。

是以我們隻需要求出每個位置的 f(i)，然後傳回 f 數組中的最大值即可。那麼我們如何求 ff(i) 呢？我們可以考慮nums[i]單獨成為一段還是加入 f(i-1) 對應的那一段，這取決nums[i] 和 f(i-1) +nums[i] 的大小，我們希望獲得一個比較大的，于是可以寫出如下的動态轉移方程，求得nums[i]，與f(i-1)+nums[i]中大的那個。

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x); // 求得f(i-1)+nums[i] 與num[i]中最大的值 （公式2）
            maxAns = max(maxAns, pre); // 求得記錄之前的值與上面的值中最大的值。 （公式1）
        }
        return maxAns;
    }
};
           

• 時間複雜度

  O(n)

• 空間複雜度

  O(1)

分治

分治思想就是将一個問題分解成為N個子問題，然後将多個解合并為一。