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

这题其实题干很多话，但是都比较花里胡哨，看起来好像很难，而且读题还很久，但是我们可以发现，里面有用的只有题目的后半段。“{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和”

由这句话我们可知，我们会被给一个数组，我们要做的就是找出这个数组里连续子数的最大和。注意是连续。
这题可以用两层循环求解，第一层我们遍历整个数组，确定现在我们找的连续数组的边界在哪里，第二层我们遍历边界前的所有数，进行相加，一旦出现数字比我们当前拥有的max大的，我们就记录下来。

这样我们可以确保最后的max是整个数组的连续子数组最大和。
这个解法有点冗余，不是最优化，会做很多已经做过的算数，但是比较简单易懂，适合小白学习。

具体代码如下：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length == 1){
            return array[0];
        }
        if(array == null){
            return 0;
        }
        int max = array[0];
        for(int i = 1; i < array.length; i++){
            if(max < array[i]){
                max = array[i];
            }
            int temp = array[i];
            int j = i-1;
            while(j >= 0){
                temp += array[j];
                if(temp > max){
                    max = temp;
                }
                j--;
            }
        }
        return max;
    }
}

如果大家觉得上面的小白解法太过简单，或者觉得自己不满足于这个解法所需要的时间，我们可以进阶到下一步，即是动态规划。这题也是动态规划比较简单，也是比较好解释动态规划的一题。

首先，在做动态规划时，我们最重要的一步，就是先创建一个和输入的array同长度的list/arraylist，用来记录到每一个元素时的最优解。
所以这题我们可以分为下面几个步骤来做动态规划解法：

  1. 新建一个长度和输入数组相同的int[] dp， 我们会在这个list里存储:到每一个元素这里，我们此刻拥有的连续字数组的最大和。同时，我们需要定义这个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
  4. 结束循环后，我们返回int max即可，这便是我们整个连续子数组的最大和

大家可以发现，用dp会相对比较没那么容易理解，但是很快，因为只有一次循环。是小白进阶的很好的选项。而且动态规划也是算法里最经典的题型。
具体代码如下：

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length == 1){
            return array[0];
        }
        if(array == null){
            return 0;
        }
        int max = array[0];
        int[] dp = new int[array.length];
        dp[0] = array[0];
        for(int i = 1; i < array.length; i++){
            int temp = dp[i-1]+array[i];
            if(temp > array[i]){
                dp[i] = temp;
            }else{
                dp[i] = array[i];
            }
            if(dp[i] > max){
                max = dp[i];
            }
        }
        return max;
    }
}