连续子数组的最大和

描述
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n).
示例1
输入：
[1,-2,3,10,-4,7,2,-5]
返回值：
18
说明：
输入的数组为{1,-2,3,10,—4,7,2,一5}，和最大的子数组为{3,10,一4,7,2}，因此输出为该子数组的和 18。

public class Solution {
//动态规划思想，pre表示第i-1元素结尾的子数组最大值，前一个状态的最大值，
    public int FindGreatestSumOfSubArray(int[] array) {
        if(array.length == 0) return 0;
        int pre = array[0];//以第i-1个元素结尾的最大值
        int max = array[0];//曾经i个元素的最大值
        for(int i = 1; i < array.length; i++){
//先比较，上一个状态的最大值+下一个元素和下一个元素哪个大，更新以第i-元素结尾的子数组最大值
            pre = Math.max(array[i], pre+array[i]);
//在比较pre和前i个元素数组的最大值。更新前i个元素的最大值。
            max = Math.max(pre,max);
        }
        return max;
    }
}