29 连续子数组的最大和

题目描述
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

代码一

思想:
这题可以用两层循环求解，
第一层我们遍历整个数组，确定现在我们找的连续数组的边界在哪里
第二层我们遍历边界前(从后向前)的所有数，进行相加，一旦出现数字比我们当前拥有的max大的，我们就记录下来。这样我们可以确保最后的max是整个数组的连续子数组最大和。

public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{-2,-8,-1,-5,-9};
        System.out.println(FindGreatestSumOfSubArray(arr));
    }
    public static int FindGreatestSumOfSubArray(int[] array) {
        //找边界
        if(array.length==1)return array[0];
        if(array.length==0)return 0;
        int max = array[0];
        for(int i = 1;i<array.length;i++)
        {
            if(array[i]>max)max=array[i];
            int j = i-1;
            int temp = array[i];
            while(j>=0) {
                temp += array[j];
                if(temp>max)max=temp;
                j--;
            }
        }
        return max;      
    }
}

如果第二层从前向后遍历的话那么要求的连续子序列都是从0索引开始

//    public static int FindGreatestSumOfSubArray(int[] array) {
//        int sum = 0;
//        int j=0;
//        int temp = 0;
//        int index = 0;
//        for(int right = 0;right<array.length;right++)
//        {
//            while(j<=right) {
//                sum += array[j];
//                j++;
//            }            
//            if(sum>=temp)
//            {
//                temp = sum;
//                index = right;
//            }
//            sum=0;
//            j=0;
//        }                
//        return index;
//            
//    }

代码一

动态规划
1、新建一个长度和输入数组相同的int[] dp， 存储连续字数组的最大和。同时，我们需要定义这个list里的第一个数是array[0]，因为第一个数只能有自己，前面没有别的数来和他形成连续子数组了。同时，我们创建一个int max，来实时记录当前的最大和。
2、遍历整个array，然后先新建一个int temp来储存当前遍历到的array[i]与前一位最大和的和，然后进行条件判断，如果这个temp大于当前的array[i]（即当前遍历到的数），我们就将temp储存入dp[i]，如果这个temp小于当前的array[i] (即如果我们只取当前这个数就已经比他加上原来所有的数都大了，我们便可以舍弃前面所有数，从这个数重新开始)，我们将array[i]储存进dp[i]里
3、在2的遍历里，当我们走完上面的判断，我们还需要判断，当前的dp[i]是不是我们至今为止的最大和，如果是，更新我们前面创建的int max
结束循环后，我们返回int max即可，这便是我们整个连续子数组的最大和

public static int FindGreatestSumOfSubArray(int[] array) {
        //动态规划
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int temp = array[0];
        int max = dp[0];
        for(int i=1;i<array.length;i++)
        {
            temp = array[i]+dp[i-1];
            if(temp<array[i]) {
                dp[i]=array[i];
            }                
            else
            {
                dp[i]=temp;
            }
            if(dp[i]>max) {
                max = dp[i];
            }
        }
        return max;
    }