剑指offer：连续子数组的最大和

题目：例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

动态规划： 

/**
 * @author :GY
 * @version :1.0
 * @ClassName :
 * @Description TODO
 * @date :Created in 2019/4/14 19:20
 * @description :连续子数组的最大和，下标不一定从0开始
 * 动态规划：通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。动态规划常常适用于有重叠子问题和最优子结构性质的问题。
 */
public class Q30 {
    public static void main(String[] args) {
        int[] array={6,-3,-2,7,-15,1,2,2};
        int [] array1={1,-2,3,-4,5,6,-7,-8,-9,12,10};
        int[] array2={-2,-8,-1,-5,-9};
        int [] array3={1,-2,3,10,-4,7,2,-5};
        int value=0;
        //value=FindGreatestSumOfSubArray(array2);
        value=FindGreatestSumOfSubArrayTest(array);
        System.out.println(value);
    }

//    动态规划-终极版
    /*
     * value=上一个最大子数组的和
     * sum=max(sum+array[i],array[i])
     * value=max(value,sum);
    *
    * 记录上一个最大子数组的和，
    * 取sum+array[i]，sum之间的最大值sum
    * 取此次的数组和与上次的数组和的最大值
    * */
    public static  int FindGreatestSumOfSubArrayTest(int[] array) {
        int sum=0;
        int value=array[0];
        for (int i=0;i<array.length;i++){
            sum=Math.max(sum+array[i],array[i]);
            value=Math.max(value,sum);
        }
        return value;
    }


//    动态规划-低级版
    /*如果sum被加上arra[i]之后。还没有array[i]大，则子序列从array[i]开始。
    * 如果sum比上一次最大和大，则更新最大值*/
    public static  int FindGreatestSumOfSubArray(int[] array) {
        if (array==null||array.length==0){
            return 0;
        }
        int sum=0;
        int value=0;
        int count=array[0];
        for (int i=0;i<array.length;i++){
            value=sum;
            sum+=array[i];
//            解决最大和的连续子数组的下标不一定是从0开始
            if(value*sum<0||sum<array[i]){
                sum=array[i];
            }
//            更换最大和
            if (count<sum){
                count=sum;
            }
        }
        return count;
    }
}