【剑指offer】连续子数组的最大和

// 不懂动态规划的小伙伴，先看书上的举例分析数组规律的部分，就会有点感觉，再看引出的动态规划部分。

【拓展】
每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到而不管之前这个状态是如何得到的 -> 动态规划。

每个阶段的最优状态可以从之前某个阶段的某个或某些状态直接得到
这个性质叫做最优子结构；

而不管之前这个状态是如何得到的
这个性质叫做无后效性。

// f(i)表示以第i个数字结尾的数组最大和。
public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        if (array == null || array.length == 0) {
            return -1;
        }
        int maxSum = array[0], t = 0;
        for (int i = 0; i < array.length; i++) {
            if (t > 0) {
                t += array[i];
            } else {
                t = array[i];
            }
            if (t > maxSum) {
                maxSum = t;
            }
        }
        return maxSum;
    }
}