题解 | #连续子数组的最大和#

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        int max = array[0];
        dp[0] = array[0];

        for (int i = 1; i < array.length; i++) {
            // 动态规划，状态转移方程，确定dp[i]的最大值
            dp[i] = Math.max(dp[i - 1] + array[i], array[i]);
            // 每次比较，保存出现的最大值
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

解题思想：动态规划，以i为结尾的作为最大连续数组的最大值，逐个求出每个位置的最大值，遍历最后得到得到结果就是最大值。