描述
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
image.png
思路：计数组的和，如果发现和小于0 就设置curSum为当前值，如果大于0 继续加
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length<= 0 ){
return 0;
}
int curSum = 0;
int maxSum = Integer.MIN_VALUE;
for(int i = 0;i<array.length;i++){
if(curSum<0){
curSum = array[i];
}else{
curSum += array[i];
}
maxSum = maxSum>curSum?maxSum:curSum;
}
return maxSum;
}
}
也可推出偏移公式 dp[i] = Math.max( dp[i-1]+array[i],array[i]);
