【剑指offer系列】42-连续子数组的最大和（关键字：O(n)、动态规划）

题目描述

{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和(子向量的长度至少是1)

public class Main42
{public static int FindGreatestSumOfSubArray(int[] array) {if (array == null || array.length == 0)return -1;int[] dp = new int[array.length];dp[0] = array[0];for (int i = 1; i < array.length; i++){if (dp[i-1] <= 0){//1.小于0就自立门户，不再有瓜葛，否则加上了arr也只会让arr变小dp[i] = array[i];}else {//2.大于0就一直累加dp[i] = dp[i - 1] + array[i];}}return Arrays.stream(dp).max().getAsInt();//3.返回最大的值}public static void main(String[] args){int[] array = {1,-2,3,10,-4,7,2,-5};System.out.println(FindGreatestSumOfSubArray(array));}
}