面试题：连续子数组最大和

题目描述：例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和

最简单：动态规划法

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array==null||array.length==0) return 0;
        int lastSum=0;
        //int maxSum=0;如果数组元素全为负数，则得不到正确值
        int maxSum=array[0];
        int start=0;
        int end=0;
        for(int i=0;i<array.length;i++){
            if(lastSum>0){
                lastSum=lastSum+array[i];
                end=i;
            }else{
                lastSum=array[i];
                start=i;
            }
            if(lastSum>maxSum)
                maxSum=lastSum;
        }
        return maxSum;
    }
}