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,1,-3,4,-1,2,1,-5,4] ， 连续子阵列 [4,-1,2,1] 的sum =最大 6 。 思想：简单的dp问题 设个数组dp[n] dp[i]:(i为下标0....n)表示前i项以元素i结尾连续的子序列的最大值 动态转移方程： dp[i-1]+sum[i] dp[i-1] >0 dp[i] = sum[i] dp[i-1]<=0 C++AC代码：时间o（n） 空间o(n) class Solution { public: int maxSubArray(vector<int>& nums) { int len = nums.size(); int dp[len]; int max; for(int i=0;i<len;i++){ if(i==0){ dp[i]=nums[i]; max = dp[i]; } else{ if(dp[i-1]>0) dp[i] = nums[i] + dp[i-1]; else dp[i] = nums[i]; } if(dp[i]>max) max = dp[i]; } return max; } }; 参考别人的代码： 也是上面的思想 只是没必要使用dp保存每一个dp[i]的状态了 因为是求最大值，所以直接用个变量动态存储就行了 时间o(n) 空间o(1) class Solution { public: int maxSubArray(vector<int>& nums) { int n = nums.size(); int ans = -2147483648; int sum = 0; for(int i=0;i<n;++i) { sum= sum+nums[i]; if(sum>ans) { ans=sum; } if(sum<0) { sum=0; } } return ans; } };
