【算法笔记】力扣热题100（LeetCode hot-100）53. 最大子数组和 1.前缀和 2.动态规划

力扣热题100（LeetCode hot-100）之 53. 最大子数组和

本文主要记录算法思路，着急要答案的同学可以直接跳转到最后的代码。

题目

给你一个整数数组 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

题解

这个问题，一般怎么解？

思路1：

使用前缀和的方法。(前缀和：即当前位置到数组第一个元素的和)

1. 定义一个变量 minPreSum，记录前缀和的最小值。（用于计算当前前缀和减去最小前缀和的最大值，默认为 0）
2. 初始化结果 res 为数组的第一个元素。
3. 遍历数组，计算当前的前缀和 sum。
4. 更新结果 res 为当前前缀和减去最小前缀和的最大值。
5. 更新最小前缀和 minPreSum。

思路2：

使用动态规划的方法。f(i)表示以第i个元素结尾的最大子数组和, f(i) = max(f(i-1) + nums[i], nums[i])。每次循环都要比较当前元素的最大子数组和和之前的最大子数组和，取最大值。

1. 定义两个变量 pre 和 result，pre 表示前一个元素的最大子数组和，result 表示当前元素的最大子数组和。
2. 遍历数组，计算当前元素的最大子数组和。
3. 如果前一个元素的最大子数组和小于 0，那么就不要加上前一个元素的最大子数组和。
4. 每次循环都要比较当前元素的最大子数组和和之前的最大子数组和，取最大值。

答案

// 思路1：前缀和
class Solution {
    public int maxSubArray(int[] nums) {
        int minPreSum = 0; // 前缀和的最小值
        int res = nums[0];
        int sum = 0; // 前缀和
        for (int n : nums) {
            sum += n; // 计算前缀和
            res = Math.max(sum - minPreSum, res); // 当前前缀和 - 前缀和的最小值，与当前最大值比较
            minPreSum = Math.min(minPreSum, sum); // 更新前缀和的最小值
        }
        return res;
    }
}

// 思路2:使用动态规划
class Solution {
    public int maxSubArray(int[] nums) {
        // pre表示前一个元素的最大子数组和，result表示当前元素的最大子数组和
        int pre = 0, result = nums[0];
        for (int num : nums) {
            // 如果前一个元素的最大子数组和小于0，那么就不要加上前一个元素的最大子数组和
            pre = Math.max(pre + num, num);
            // 每次循环都要比较当前元素的最大子数组和和之前的最大子数组和，取最大值
            result = Math.max(result, pre);
        }
        return result;
    }
}