问题描述 ：

输入一个整数数组，数组里面有正数也有负数。数组中一个或连续几个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为O(n)

思路1：常规解法，不知道怎么描述了。。

代码：

boolean invalidInput = false;

    public int FindGreatestSumOfSubArray(int[] array) {

        if(array == null || array.length == 0){

            invalidInput = true;

            return 0;

        }

        int currentSum = 0;

        int greatestSum = 0x80000000;

        for(int i = 0; i < array.length; i++){

            if(currentSum < 0){

                currentSum = array[i];

            }else{

                currentSum += array[i]

            }

            if(currentSum > greatestSum){

                greatestSum = currentSum;

            }

        }

        return greatestSum;

    }

思路2：动态规划

如果用函数f(i)表示以第i个数字结尾的子数组的最大和，那么我们需要求出max[f(i)],其中0<=i小于n.

递归公式如下：

f(i) = :pData[i] 当 i = 0或者f(i-1)<=0

:f(i-1)+pData[i] 当i不等于0或者f(i-1)>0

第二种解法代码与第一种其实是一样的。