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

这题要求最值，首先应该想到的就是动态规划，动态规划擅长解决这类问题。

第一种方法：数组的元素依次相加，如果和大于0则可以继续向后加，因为前面的值为正值是可以对后面的求和有正向作用。一旦小于0了，则应该放弃这个sum。在这个过程中一直记录最大值。

第二种方法：动态规划。难点就在于如何定义状态？如果dp[n]表示第n个位置的最大和，那么将无法设计状态转移方程，因为前一个状态没有好的办法转移到新的状态。

这里的技巧就在于用 dp[n] 表示以第n个数字结尾的最长连续子数组的最大和，这样前后两个状态就可以连续起来。那么最终结果就是遍历 dp 数组获得其中的最大值就是答案。

状态转移方程：dp[n] = Math.max(array[n], dp[n - 1] + array[n]);

public class Solution {
    private int one(int[] array) {
        int max = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < array.length; i++) {
            sum += array[i];
            if (sum > 0) {
                if (sum > max) {
                    max = sum;
                }
            } else {
                sum = 0;
                if (array[i] > max) {
                    max = array[i];
                }
            }
        }
        return max;
    }
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = dp[0];
        // dp[n] 表示以第n个值结尾的连续数组最大值
        for (int n = 1; n < array.length; n++) {
            dp[n] = Math.max(array[n], dp[n - 1] + array[n]);
            max = Math.max(max, dp[n]);
        }
        return max;
    }
}