1. 题目描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

2. 解题思路

动态规划，计算 以nums[i]结尾的最大子串和sum[i],然后数组中最大的值就是结果。 迭代方程： if sum[i-1]>0: sum[i]=nums[i]+sum[i-1] else: sum[i]=nums[i]

3. 实现代码

class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); int sum=0; int max_sum=INT_MIN; for(int i=0;i<n;i++){ if(sum>=0){ sum+=nums[i]; }else{ sum=nums[i]; } if(sum>max_sum){ max_sum=sum; } } return max_sum; } };