class Solution {
public:
int maxSubArray(vector<
int>&
nums) {
int pre=nums[
0];
//int now;
int maxSum=nums[
0];
for(
int i=
1;i<nums.size();i++
){
if(pre>
0){
pre+=
nums[i];
}
else{
pre=
nums[i];
}
if(pre>
maxSum){
maxSum=
pre;
}
}
return maxSum;
}
};
View Code
如果之前的和大于0，那么加上它。否则，舍弃，pre为当前数。
如果加了之后比已知的最大和大，那么最大和是加了之后的和。
……我也忘了怎么想出来的。
动态规划嘛，从1到n。找出i+1相对于i的变化。
如果前面的和 < 0，前面没有。
大于0，那么好，加上。
最大和用maxSum保存，然后比较加上是否比它大。
还可以用分治，O(nlogn)
转载于:https://www.cnblogs.com/azureice/p/leetcode53.html
