LeetCode 53. 最大子数组和【前缀和+贪心；动态规划】中等

memcpy0

909人浏览 · 2020-06-28 22:20:03

memcpy0 · 2020-06-28 22:20:03 发布

本文属于「征服LeetCode」系列文章之一，这一系列正式开始于2021/08/12。由于LeetCode上部分题目有锁，本系列将至少持续到刷完所有无锁题之日为止；由于LeetCode还在不断地创建新题，本系列的终止日期可能是永远。在这一系列刷题文章中，我不仅会讲解多种解题思路及其优化，还会用多种编程语言实现题解，涉及到通用解法时更将归纳总结出相应的算法模板。

为了方便在PC上运行调试、分享代码文件，我还建立了相关的仓库：https://github.com/memcpy0/LeetCode-Conquest。在这一仓库中，你不仅可以看到LeetCode原题链接、题解代码、题解文章链接、同类题目归纳、通用解法总结等，还可以看到原题出现频率和相关企业等重要信息。如果有其他优选题解，还可以一同分享给他人。

由于本系列文章的内容随时可能发生更新变动，欢迎关注和收藏征服LeetCode系列文章目录一文以作备忘。

给你一个整数数组 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 <= 10^5
-10^4 <= nums[i] <= 10^4

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

解法1 前缀和+贪心

由于子数组的元素和等于两个前缀和的差，所以求出 $n u m s$ 的前缀和，问题就变成[[LeetCode 121. Best Time to Buy and Sell Stock【单调栈;树状数组;动态规划】简单]]。本题子数组不能为空，相当于一定要交易一次。

我们可一边遍历数组计算前缀和，一边维护前缀和的最小值（相当于股票最低价格），用当前的前缀和（卖出价格）减去前缀和的最小值（买入价格），就得到了以当前元素结尾的子数组和的最大值（利润），用它更新答案的最大值（最大利润）。

注意，由于题目要求子数组不能为空，应当先计算前缀和-最小前缀和，再更新最小前缀和。相当于不能在同一天买入股票又卖出股票。如果先更新最小前缀和，再计算前缀和-最小前缀和，就会把空数组的元素和 $0$ 算入答案。

问：为什么不能直接计算出最大前缀和与最小前缀和，二者相减不就是答案吗？
答：这是错的。子数组的和必须是右边的前缀和减去左边的前缀和。如果最大前缀和在左边，最小前缀和在右边，就不符合要求。例如 $n u m s = [1, - 2]$ ，最大子数组和是 $1$ ，如果用最大前缀和 $1$ 减去最小前缀和 $- 1$ ，结果是错误的 $2$ 。

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE;
        int minPreSum = 0;
        int preSum = 0;
        for (int x : nums) {
            preSum += x; // 当前的前缀和
            ans = Math.max(ans, preSum - minPreSum); // 减去前缀和的最小值
            minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值
        }
        return ans;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN;
        int min_pre_sum = 0;
        int pre_sum = 0;
        for (int x : nums) {
            pre_sum += x; // 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum); // 维护前缀和的最小值
        }
        return ans;
    }
};

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf
        min_pre_sum = pre_sum = 0
        for x in nums:
            pre_sum += x  # 当前的前缀和
            ans = max(ans, pre_sum - min_pre_sum)  # 减去前缀和的最小值
            min_pre_sum = min(min_pre_sum, pre_sum)  # 维护前缀和的最小值
        return ans

func maxSubArray(nums []int) int {
    ans := math.MinInt
    minPreSum := 0
    preSum := 0
    for _, x := range nums {
        preSum += x // 当前的前缀和
        ans = max(ans, preSum-minPreSum)   // 减去前缀和的最小值
        minPreSum = min(minPreSum, preSum) // 维护前缀和的最小值
    }
    return ans
}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut ans = i32::MIN;
        let mut min_pre_sum = 0;
        let mut pre_sum = 0;
        for x in nums {
            pre_sum += x; // 当前的前缀和
            ans = ans.max(pre_sum - min_pre_sum); // 减去前缀和的最小值
            min_pre_sum = min_pre_sum.min(pre_sum); // 维护前缀和的最小值
        }
        ans
    }
}

var maxSubArray = function(nums) {
    let ans = -Infinity;
    let minPreSum = 0;
    let preSum = 0;
    for (const x of nums) {
        preSum += x; // 当前的前缀和
        ans = Math.max(ans, preSum - minPreSum); // 减去前缀和的最小值
        minPreSum = Math.min(minPreSum, preSum); // 维护前缀和的最小值
    }
    return ans;
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))
#define MIN(a, b) ((b) < (a) ? (b) : (a))

int maxSubArray(int* nums, int numsSize) {
    int ans = INT_MIN;
    int min_pre_sum = 0;
    int pre_sum = 0;
    for (int i = 0; i < numsSize; i++) {
        pre_sum += nums[i]; // 当前的前缀和
        ans = MAX(ans, pre_sum - min_pre_sum); // 减去前缀和的最小值
        min_pre_sum = MIN(min_pre_sum, pre_sum); // 维护前缀和的最小值
    }
    return ans;
}

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为 $n u m s$ 的长度。
空间复杂度： $O (1)$ 。仅用到若干额外变量。

解法2 动态规划

定义 $f [i]$ 表示以 $n u m s [i]$ 结尾的最大子数组和。

分类讨论：

$n u m s [i]$ 单独组成一个子数组，那么 $f [i] = n u m s [i]$ 。
$n u m s [i]$ 和前面的子数组拼起来，也就是在以 $n u m s [i - 1]$ 结尾的最大子数组和之后添加 $n u m s [i]$ ，那么 $f [i] = f [i - 1] + n u m s [i]$ 。

两种情况取最大值，得
$f[i]=\begin{cases} nums[i], &\quad i = 0 \\ \max (f[i−1],0) + nums[i] &\quad i≥1 \end{cases}$
简单地说，如果 $n u m s [i]$ 左边的子数组元素和是负的，就不用和左边的子数组拼在一起了。

答案为 $\max(f)$ 。

⚠注意：答案不是 $f [n - 1]$ ，这仅仅表示以 $n u m s [n - 1]$ 结尾的最大子数组和。或者说 $f [n - 1]$ 意味着 $n u m s [n - 1]$ 一定要选，但这不一定正确。

问：为什么不能用「选或不选 $n u m s [i]$ 」的思路做？
答：选或不选无法保证子数组是连续的。选或不选适用于子序列问题（例如 0-1 背包问题），对于子数组问题，更适合用「拼接」的思路，即如果 $n u m s [i]$ 左边的子数组元素和是负的，就不用和左边的子数组拼在一起了。

优化前

class Solution {
    public int maxSubArray(int[] nums) {
        int[] f = new int[nums.length];
        f[0] = nums[0];
        int ans = f[0];
        for (int i = 1; i < nums.length; i++) {
            f[i] = Math.max(f[i - 1], 0) + nums[i];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        vector<int> f(nums.size());
        f[0] = nums[0];
        for (int i = 1; i < nums.size(); i++) {
            f[i] = max(f[i - 1], 0) + nums[i];
        }
        return ranges::max(f);
    }
};

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        f = [0] * len(nums)
        f[0] = nums[0]
        for i in range(1, len(nums)):
            f[i] = max(f[i - 1], 0) + nums[i]
        return max(f)

func maxSubArray(nums []int) int {
    f := make([]int, len(nums))
    f[0] = nums[0]
    for i := 1; i < len(nums); i++ {
        f[i] = max(f[i-1], 0) + nums[i]
    }
    return slices.Max(f)
}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut f = vec![0; nums.len()];
        f[0] = nums[0];
        for i in 1..nums.len() {
            f[i] = f[i - 1].max(0) + nums[i];
        }
        *f.iter().max().unwrap()
    }
}

var maxSubArray = function(nums) {
    const f = Array(nums.length);
    f[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        f[i] = Math.max(f[i - 1], 0) + nums[i];
    }
    return Math.max(...f);
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int maxSubArray(int* nums, int numsSize) {
    int* f = malloc(numsSize * sizeof(int));
    f[0] = nums[0];
    int ans = f[0];
    for (int i = 1; i < numsSize; i++) {
        f[i] = MAX(f[i - 1], 0) + nums[i];
        ans = MAX(ans, f[i]);
    }
    free(f);
    return ans;
}

空间优化

由于计算 $f [i]$ 只会用到 $f [i - 1]$ ，不会用到更早的状态，所以可用一个变量滚动计算。状态转移方程简化为： $\max(f, 0) + nums[i]$
$f$ 可以初始化为 $0$ 或任意负数。

class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE; // 注意答案可以是负数，不能初始化成 0
        int f = 0;
        for (int x : nums) {
            f = Math.max(f, 0) + x;
            ans = Math.max(ans, f);
        }
        return ans;
    }
}

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int ans = INT_MIN; // 注意答案可以是负数，不能初始化成 0
        int f = 0;
        for (int x : nums) {
            f = max(f, 0) + x;
            ans = max(ans, f);
        }
        return ans;
    }
};

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = -inf  # 注意答案可以是负数，不能初始化成 0
        f = 0
        for x in nums:
            f = max(f, 0) + x
            ans = max(ans, f)
        return ans

func maxSubArray(nums []int) int {
    ans := math.MinInt // 注意答案可以是负数，不能初始化成 0
    f := 0
    for _, x := range nums {
        f = max(f, 0) + x
        ans = max(ans, f)
    }
    return ans
}

impl Solution {
    pub fn max_sub_array(nums: Vec<i32>) -> i32 {
        let mut ans = i32::MIN; // 注意答案可以是负数，不能初始化成 0
        let mut f = 0;
        for x in nums {
            f = f.max(0) + x;
            ans = ans.max(f);
        }
        ans
    }
}

var maxSubArray = function(nums) {
    let ans = -Infinity; // 注意答案可以是负数，不能初始化成 0
    let f = 0;
    for (const x of nums) {
        f = Math.max(f, 0) + x;
        ans = Math.max(ans, f);
    }
    return ans;
};

#define MAX(a, b) ((b) > (a) ? (b) : (a))

int maxSubArray(int* nums, int numsSize) {
    int ans = INT_MIN; // 注意答案可以是负数，不能初始化成 0
    int f = 0;
    for (int i = 0; i < numsSize; i++) {
        f = MAX(f, 0) + nums[i];
        ans = MAX(ans, f);
    }
    return ans;
}

复杂度分析：

时间复杂度： $O (n)$ ，其中 $n$ 为 $n u m s$ 的长度。
空间复杂度： $O (1)$

思考题

1、改成求最小子数组和，应当如何修改代码？
2、改成返回和最大的子数组，要怎么做？注意返回的是子数组，不是元素和。
3、如果子数组的长度有下界，要怎么做？
4、如果子数组的长度有上界，要怎么做？
5、如果要求子数组的长度必须是奇数，要怎么做？

变形题

1、子数组的元素和有上界。见 [[LeetCode 363. 矩形区域不超过 K 的最大数值和【二维前缀和+枚举+二分】困难]] 。提示：枚举上下边界，转成一维数组。
2、拼接 $k$ 个相同的 $n u m s$ ，得到一个长为 $nk$ 的大数组，求这个大数组的最大子数组和。见 [[1191. K 次串联后最大子数组之和]]。
3、 $n u m s$ 是个环形数组。见 [[LeetCode 918. Maximum Sum Circular Subarray【数组,动态规划】中等]] 。
4、删除 $n u m s$ 中的至多一个数，再求最大子数组和。见 [[LeetCode C++ 1186. Maximum Subarray Sum with One Deletion【动态规划】中等]] 。

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

基于模型预测+强化学习（混合MPC-RL）、NMPC、MPC控制的无人机轨迹跟踪任务、评估UAV跟踪移动平台任务的性能研究（Matlab代码实现）

针对无人机对移动平台高精度轨迹跟踪任务中存在的模型非线性、外部扰动以及动态约束适配性差等问题，本文提出一种模型预测控制与强化学习融合的混合控制策略。通过构建无人机六自由度非线性动力学模型并完成局部线性化处理，分别设计线性模型预测控制、非线性模型预测控制、纯强化学习控制以及混合 MPC-RL 控制器，依托 Simulink 与 MATLAB 脚本联合仿真环境开展对比试验。

AtomGit开源社区

双连杆机械臂 RBFNN-NTSM 自适应强化学习控制算法（Matlab代码实现）

针对双连杆机械臂在模型不确定性、外部扰动以及执行器饱和约束下的高精度轨迹跟踪控制难题，本文提出一种融合径向基函数神经网络、非奇异终端滑模控制与强化学习的自适应鲁棒控制方案。该方法以非奇异终端滑模为核心控制框架，保证系统状态在有限时间内收敛并避免传统滑模的奇异性问题；采用评价 - 动作双网络强化学习结构，利用径向基函数神经网络实现对系统未知动态与不确定项的在线逼近，同时完成控制策略的自适应优化；设计

AtomGit开源社区

不平衡学习的自适应合成采样方法ADASYN（Matlab代码实现）

在机器学习实际应用中，类别不平衡问题广泛存在，即数据集中某一类别的样本数量远多于另一类别（多数类与少数类），这种不平衡分布会导致模型训练偏向多数类，大幅降低少数类样本的识别精度，而少数类样本往往承载着关键信息（如欺诈检测中的欺诈样本、医疗诊断中的患病样本）。自适应合成采样方法（ADASYN）作为解决类别不平衡问题的经典过采样技术，通过自适应调整少数类样本的合成策略，重点关注难以学习的少数类样本，有