题目描述

解题思路

暴力解法

第一层for 就是设置起始位置，第二层for循环遍历数组寻找最大值。

贪心解法

局部最优：当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
全局最优：选取最大“连续和”
局部最优的情况下，并记录最大的“连续和”，可以推出全局最优。
从代码角度上来讲：遍历nums，从头开始用count累积，如果count一旦加上nums[i]变为负数，那么就应该从nums[i+1]开始从0累积count了，因为已经变为负数的count，只会拖累总和。

/**
         * 贪心法（O（n）时间复杂度）
         *
         * @param nums
         * @return
         */
public int maxSubArray(int[] nums) {
    int result = Integer.MIN_VALUE; // 表示最大的结果集
    int count = 0;  // 总和
    for (int i = 0; i < nums.length; i++) {
        count += nums[i];
        if (count > result) {
            result = count;
        }
        // 贪心贪的地方：当总和小于0时，此时和为负数只会减少后面总和大小，所以需要重新计算连续和
        if (count < 0) {
            count = 0;
        }
    }
    return result;
}

动态规划

public int maxSubArray(int[] nums) {
    if (nums.length == 1) {
        return nums[0];
    }
    // dp[i]：包括下标i之前的最大连续子序列和为dp[i]
    int[] dp = new int[nums.length];
    dp[0] = nums[0];
    // 初始化为第一个表示最大总和，满足例如[-1,-2]
    int result = dp[0];
    for (int i = 1; i < nums.length; i++) {
        //                dp[i]只有两个方向可以推出来：
        //                dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
        //                nums[i]，即：从头开始计算当前连续子序列和
        //                一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);
        dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
        if (dp[i] > result) result = dp[i]; // 取出最大的
    }
    return result;
}