給定一個(gè)整數(shù)數(shù)組 nums 灼捂，找到一個(gè)具有最大和的連續(xù)子數(shù)組（子數(shù)組最少包含一個(gè)元素），返回其最大和阎曹。
示例:
輸入: [-2,1,-3,4,-1,2,1,-5,4],
輸出: 6
解釋: 連續(xù)子數(shù)組 [4,-1,2,1] 的和最大伪阶，為 6。
思路：
動(dòng)態(tài)規(guī)劃处嫌，dp[i]為以nums[i]元素結(jié)尾的最大子序和栅贴，則為以下幾種情況：
1.若i=0 則dp[i]=nums[i]
2.若i!=0且dp[i-1]<=0 則dp[i]=nums[i]
3.若i=0且dp[i-1]>0 則dp[i]=nums[i]+dp[i-1]
具體實(shí)現(xiàn)如下。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int len=nums.size();
vector<int> dp(len,0);
if(!len)
{
return 0;
}
int res=INT_MIN;
for(int i=0;i<len;i++)
{
if(!i)
{
dp[i]=nums[i];
}
else
{
if(dp[i-1]<=0)
{
dp[i]=nums[i];
}
else
{
dp[i]=nums[i]+dp[i-1];
}
}
res=max(res,dp[i]);
}
return res;
}
};
