输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
动态规划类：
只有1个元素的话，那肯定就是这个元素。
增加1个元素后，如何与原来的小规模问题关联？
假定为数组a
c[i]代表以a[i]结尾的，连续子数组的最大和。
c[i]=max{c[i-1]+a[i],a[i]}
class Solution {
public int maxSubArray(int[] nums) {
//分解子问题
int res = nums[0];
for(int i = 1;i< nums.length;i++){
if(nums[i-1]>0){
nums[i] += nums[i-1];
}
if(res < nums[i]){
res = nums[i];
}
}
return res;
}
}
网友评论