給一個數(shù)組，返回它的最大連續(xù)子序列的和。例如 [6,-3,-2,7,-15,1,2,2] 連續(xù)子序列的最大和為 8（從第 0 個開始，到第 3 個為止)。注意：連續(xù)子序列的起始下標不一定是 0。

解題思路

采用動態(tài)規(guī)劃的思想，假設(shè) dp[n] 表示以當前元素為截止點的連續(xù)子序列的最大和，那么可以得出狀態(tài)轉(zhuǎn)移方程 dp[n] = dp[n - 1] + array[n]

題目只要求最大值，因此每次都可以使用一個變量 max 記錄最大和，變量 res 記錄當前子序列的最大和，再將 max 與 res 比較，將更大的值賦給 max，最后返回 max 即可

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int res = array[0];
        int max = array[0];
        for(int i = 1; i < array.length; i++) {
        	// 當前子序列的最大和，要么是前一個子序列加上當前值，要么只是當前值
            res = Math.max(res + array[i], array[i]);
            max = Math.max(res, max);
        }
        return max;
    }
}