LeetCode 53. 最大子序和（動态規劃）

1. 題目描述

題目連結：https://leetcode-cn.com/problems/maximum-subarray/

《劍指Offer》同題：面試題42. 連續子數組的最大和

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

輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續子數組 [4,-1,2,1] 的和最大，為 6。           

複制

進階:

如果你已經實作複雜度為 O(n) 的解法，嘗試使用更為精妙的分治法求解。

2. 解題

類似題目：程式員面試金典 - 面試題 17.24. 最大子矩陣（轉成一維最大子序和 DP）

2.1 暴力求解

雙重循環O（n2）時間複雜度

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
        if(nums.size() == 0) 
            return 0;
        int max = nums[0];//最大值
        int sum=0, i, j;
        for(i = 0; i< nums.size(); ++i)
        {
            sum=0;
            for(j = i; j< nums.size(); ++j)
            {
                sum += nums[j];
                if(sum > max) //實時更新最大值
                    max = sum;
            }
        }
        return max;
    }
};           

複制

2.2 動态規劃

狀态轉移方程

m a x s u m [ i ] = m a x ( m a x s u m [ i − 1 ] + n u m [ i ] , n u m [ i ] ) maxsum[i] = max( maxsum[i-1] + num[i], num[i] ) maxsum[i]=max(maxsum[i−1]+num[i],num[i])

表示到i元素，最大子序列和的最大值

把所有maxsum[i]的元素最大值傳回就是答案

if maxsum[i-1] + num[i] >= num[i]	//num[i]起
	maxsum[i] = maxsum[i-1] + num[i]
else 
	maxsum[i] = num[i]

maxSumOfSubArr = max{maxsum[0],maxsum[i]...maxsum[n-1]}           

複制

時間複雜度O（n）

i	1	2	3	4	5	6	7	8
nums[i]	-2	1	-3	4	-1	2	1	-5	4
maxsum[i]	-2	max(-2+1,1)=1	max(1-3,-3)= -2	4	3	5	6	1	5

class Solution
{
public:
    int maxSubArray(vector<int>& nums)
    {
        int maxSumOfArr = INT_MIN, maxsum = 0;
        for(int i = 0; i < nums.size(); ++i)
        {
            maxsum = max(nums[i],maxsum+nums[i]);
            maxSumOfArr = max(maxSumOfArr, maxsum);
        }
        return maxSumOfArr;
    }
};           

複制

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int i, n = nums.size(), ans = nums[0];
        vector<int> dp(n,0);
        dp[0] = nums[0];
        for(i = 1; i < n; ++i)
        {
        	if(dp[i-1] >= 0)
        		dp[i] = nums[i]+dp[i-1];
        	else
        		dp[i] = nums[i];
        	ans = max(ans,dp[i]);
        }
        return ans;
    }
};           

複制