leetcode 53 Maximum Subarray
给定一个数组（至少包含一个整数），找出一个该数组的连续子数组，并且该连续子数组的和最大，返回最大值。
算法
同样使用动态规划解题，找出状态n和n-1之间的关系，然后从0到n-1遍历一遍得到结果
状态n和n-1的关系
在每个状态下记录两个值，一个是当前的最大值largest，一个是当前的连续子数组的和nowsum
nowsum(n)=nums[n] nowsum(n-1)<0,
nowsum(n-1)+nums[n] nowsum(n-1)>=0.
largest(n)=max(largest(n-1), nowsum(n)).
初始状态
largest(0)=nowsum(0)=nums[0].
code
class Solution {
public:
int maxSubArray(
vector<int>& nums) {
int largestsum = nums[
0], nowsum = nums[
0];
for (
int i =
1; i < nums.size(); i++){
if(nowsum<
0){
nowsum = nums[i];
}
else{
nowsum += nums[i];
}
largestsum = max(largestsum, nowsum);
}
return largestsum;
}
};
算法时间复杂度： O（n）
