一看就会：最大自序和状态压缩算法

代码宇宙

发布于 2023-02-23 10:11:20

3180

原题如下：

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

示例:

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

方法一、暴力解法

比较容易想到的是用“暴力解法”做，即穷举所有的子区间。思路虽然简单，但是写好暴力解法也不是一件容易的事情。

使用双层循环，穷举所有的子区间；
然后再对子区间内的所有元素求和；
时间复杂度是立方级别的。

参考代码 1：

这里要注意一些边界条件：

变量 i 表示结尾的那个索引；
变量 j 表示从索引 0 依次向前走；

class Solution {
private:
    int sumOfArray(vector<int> &nums, int left, int right) {
        int res = 0;
        for (int i = left; i <= right; ++i) {
            res += nums[i];
        }
        return res;
    }
public:
    int maxSubArray(vector<int> &nums) {
        int size = nums.size();
        int res = INT_MIN;
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j <= i; ++j) {
                int sum = sumOfArray(nums, j, i);
                res = max(res, sum);
            }
        }
        return res;
    }
};

暴力解法，仅仅作为参考，我们不做更多评论，主要来看一下，动态规划中的动态压缩

方法二、动态规划

核心：我们只需要一个变量subMax保存前面子组合的最大值，另外一个max保存全局最大值。

动态图解：

首先初始化全局最大值和前一个子组合的最大值为数组的第一个值。

然后循环遍历数组，取到第二个，如果最大值>0，可以给第二个值带来增益，那么最大值变为 max+第二个值，如果最大值 <0，那么不能给第二个值带来增益，那么就将第二个值把最大值直接替换，打个确切的比方。

伪代码如下

arr = [-2,1,-3,4,-1,2,1,-5,4]

max = 数组第一个元素，也就是 -2

subMax = 数组第一个元素，也就是 -2

第一次循环{

取 arr[i] 这里是 1

因为 -2<0

所以 subMax = 1

max =1

}

第二次循环{

取 arr[i] 这里是 -3

因为 1 > 0

所以 subMax = -2

max = -2

}

第三次循环{

取 arr[i] 这里是 4

因为 -2< 0

所以 subMax = 4

max = 4

}

...

继续按照这个套路执行.....

最终执行完毕，max 值即为最大子序和（6），是不是很容易理解？

真实代码（Java）

参数为：[-2,1,-3,4,-1,2,1,-5,4]

public int maxSubArray(int[] nums) {
    if (nums == null) {
        return 0;
    }
    int max = nums[0];    // 全局最大值
    int subMax = nums[0];  // 前一个子组合的最大值,状态压缩
    for (int i = 1; i < nums.length; i++) {
        if (subMax > 0) {
            // 前一个子组合最大值大于0，正增益
            subMax = subMax + nums[i];
        } else {
            // 前一个子组合最大值小于0，抛弃前面的结果
            subMax = nums[i];
        }
        // 计算全局最大值
        max = Math.max(max, subMax);
    }

    return max;
}

欢迎关注公众号：代码宇宙，一看就会系列算法将会持续更新~

扩展资料：

https://www.cnblogs.com/genius777/p/8470411.html

https://leetcode-cn.com/problems/maximum-subarray/solution/zheng-li-yi-xia-kan-de-dong-de-da-an-by-lizhiqiang/?from=groupmessage

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2020-03-20，如有侵权请联系 cloudcommunity@tencent.com 删除

https