面试题42：连续子序列的最大和

输入一个整型数组，数组里正负数都可能有，数组中的一个或者连续的多个整数组成一个子数组。

• 求所有子数组的和的最大值，要求时间复杂度为O(n)

思路一：
采用一个比较记录最大和，一个记录当前位置数组之前序列的和。如果前一个和小于0，避让比当前数字开始的子数组和要小，直接从当前位置再开始。
代码如下：

/**
     * 普通累加算法
     * @param array
     * @return
     */
    public static int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) return 0;
          int curSum = array[0];
          int maxSum = array[0];
          for (int i=1;i<array.length;i++){
              if (curSum < 0) curSum = array[i];
              else {
                  curSum += array[i];
              }
              if (curSum > maxSum) maxSum = curSum;
          }
          return maxSum;
    }

思路二：动态规划
赋初值以后，如果从当前数组第二个开始，每次只取当前和数组位置的累加和与当前数组值中最大的那个
最大和数值每次再取自身与当前数组和最大的一个。
最后返回最大和。

/**
     * 动态规划
     * @param array
     * @return
     */
    public static int FindGreatestSumOfSubArray1(int[] array) {
        if (array == null || array.length == 0) return 0;
        int curSum = array[0];
        int maxSum = array[0];
        for (int i=1;i<array.length;i++){
            curSum = Math.max(curSum+array[i],array[i]);
            maxSum = Math.max(curSum,maxSum);
        }
        return maxSum;
    }

    public static void main(String[] args) {
        int[] a = {6,-3,-2,7,-15,1,2,2};
        System.out.println(FindGreatestSumOfSubArray(a));
        System.out.println(FindGreatestSumOfSubArray1(a));
    }