【53】最大子数组和【LeetCode】

1.题目描述

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

输入：nums = [1]
输出：1

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

提示：

• 1 <= nums.length <= 105

• -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

1.动态规划的空间优化

这题是典型的动态规划题目, 最困难的点在于 dp数组的定义及下标含义用ai代表nums[i], 用f(i)代表以第i个数结尾的「连续子数组的最大和」, 网上也有很多文章介绍了是如何一步步分析来获得定义的过程的, 但我感觉对于新手来说, 可能还是多见一些类似的题目, 获得大量的经验, 这样比较有效果吧, 毕竟想研究动态规划的理论基础还是挺有难度的.

动态规划最重要的思想就是**利用上一个状态, 对于本题而言就是: 到底要不要加上上一个状态f(i-1)的信息, 这完全取决于f(i-1)的正负情况, 这样我们就能得出了动态规划的递推公式: f(i)=max{f(i−1)+ai,ai}

得到了递推公式后就可以编写代码了, 代码中的一个技巧就是对于空间复杂度的优化. 当使用动态规划只需要一个数(并不需要整个dp数组)时, 我们就没必要将整个dp数组都保存下来, 我们只需用变量来记录下我们需要的某个量即可, 这个优化方法在动态规划中还是非常常用的方法, 具体的实现参考代码.

2.贪心法的思想

本题还可以利用贪心法来实现, 贪心的思想是: 从左向右迭代, 一个个数字加过去如果sum<0, 那说明加上它只会变得越来越小, 所以我们将sum置零后重新开始找子序串.

在迭代的过程中要注意, 我们需要用result来不断维持当前的最大子序和, 因为sum的值是在不断更新的, 所以我们要及时记录下它的最大值.

有一个注意点是: 有的朋友可能觉得当数组全是负数的时候可能会出现问题, 其实是没有问题的. 因为在sum不断遍历的过程中, 早已将最大值不断传给result, 即使sum一直是负数被不断置零也不用担心, result还是会记录下最大的那个负数.

2.核心代码​​​​​​​

 1. 贪心法  

在Java中，整数类型的大小是有范围的。

最大值为Integer.MAX_VALUE，即2147483647。

最小值为Integer.MIN_VALUE ，即-2147483648。

// 贪心法
class Solution {
    public int maxSubArray(int[] nums) {
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int result = Integer.MIN_VALUE;
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            result = Math.max(result, sum);
            //如果sum < 0,重新开始找子序串
            if (sum < 0) {
                sum = 0;
            }
        }
        return result;
    }
}

 2. 动态规划法  

// 动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            //pre来维护对于当前f(i)的f(i−1)的值是多少
            pre = Math.max(pre + x, x);//判断f(i-1)是否要加到当前数上
            maxAns = Math.max(maxAns, pre);//获取最大值
        }
        return maxAns;
    }
}

3.测试代码​​​​​​​

 1. 贪心法  

// 贪心法
class Solution {
    public int maxSubArray(int[] nums) {
        //类似寻找最大最小值的题目,初始值一定要定义成理论上的最小最大值
        int result = Integer.MIN_VALUE;
        int len = nums.length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            sum += nums[i];
            result = Math.max(result, sum);
            //如果sum < 0,重新开始找子序串
            if (sum < 0) {
                sum = 0;
            }
        }
        return result;
    }
}
// @solution-sync:end

class Main {

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int result = new Solution().maxSubArray(nums);
        System.out.println(result);
    }

}

 2. 动态规划法   

// 动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            //pre来维护对于当前f(i)的f(i−1)的值是多少
            pre = Math.max(pre + x, x);//判断f(i-1)是否要加到当前数上
            maxAns = Math.max(maxAns, pre);//获取最大值
        }
        return maxAns;
    }
}
// @solution-sync:end

class Main {

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};

        int result = new Solution().maxSubArray(nums);
        System.out.println(result);
    }

}