算法动态规划

最大子数组和的三种解法

字数统计: 1.6k字   |   阅读时长: 7分
, ,

摘要: 本文介绍非常基础的最大子数组和，有动态规划、分治、前缀和三种解法。

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文我们看一个非常经典也是非常基础的一道题，力扣53-最大子数组和，一般在接触动态规划没多久肯定就遇到这个题了。除了动态规划以外，本题还有分治和前缀和这两种做法，

最大子数组和还有很多变种问题，变种问题基本上也都是基于这三种解法做适当修改后解决的。例如：

  • 环形上的最大子数组和-力扣918
  • 最大子数组乘积-力扣152
  • 最大子矩阵和-面试题17.24
  • 带大小限制的最大子矩阵和-力扣363
  • 增删改后的最大子数组和-力扣1191、力扣1186
  • 子数组和的绝对值的最大值-力扣1749
  • 可以修改正负号时的子数组和的绝对值的最大值-LCP65

我们循序渐进，本文我们先解决最基本的问题，之后的几篇文章我们集中看一下几个变种问题。最后我们解决最难的一个变种问题，上面的 LCP 65，也就是这次秋季赛的最后一题。

题目

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

样例：

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

题解

算法1: 动态规划(Kadane 算法)

Kadane 是卡耐基梅隆大学的统计学的教授，他在 1984 年提出提出的这个算法。该算法是在数组或滑动窗口中找到子串和的最大值或最小值的 O(N) 算法。这个算法看起来有个专有名字，好像很复杂，其实就是基于动态规划的，也就是说我们自己按照动态规划的速录来做的话，也能得到相同的算法，

kadane

动态规划算法如下：

1
2
3
4
5
6
7
8
9
10
11
状态定义：
dp[i] := [0..i] 中，以 nums[i] 结尾的最大子串和

答案:
max(dp[i])

初始化：
dp[0] = nums[0]

状态转移：
dp[i] = nums[i] + max(dp[i - 1], 0)

因为求 dp[i] 时只用到了 dp[i - 1]，所以dp数组可以压缩掉，只用一个变量 sum 维护状态。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        // 调用方保证 nums 不为空
        int n = nums.size();
        int sum = 0; // 当前的子串和
        int ans = INT_MIN; // 当前的最大子串和
        for(int i = 0; i < n; ++i)
        {
            sum = nums[i] + max(sum, 0);
            ans = max(ans, sum);
        }
        return ans;
    }
};

算法2: 前缀和+单调队列

将 A[0..n-1] 的前缀和 sums[0..n] 求出之后，枚举每个前缀和的下标 1 <= j <= n，找到 0 < j - i <= N 时最大的 sums[j] - sums[i] 即为以 A[j - 1] 为结尾的最大子数组和，也就是要找最小的 sums[i]。

摊销 O(1) 地找到每个 j 的左侧最值及其下标 i，其中 i 的范围需要满足某些条件(这里是 j - i <= N)。这正是单调队列的场景。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        deque<int> deq;
        vector<int> sums(n + 1, 0);
        for(int i = 0; i < n; ++i)
            sums[i + 1] = nums[i] + sums[i];
        int ans = INT_MIN;
        deq.push_back(0);
        for(int j = 1; j <= n; ++j)
        {
            int pj = sums[j];
            int pi = sums[deq.front()];
            ans = max(ans, pj - pi);
            while(!deq.empty() && sums[deq.back()] >= pj)
                deq.pop_back();
            deq.push_back(j);
            if(j - deq.front() == n)
                deq.pop_front();
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 1) return nums[0];
        deque<int> deq;
        vector<int> sums(n + 1, 0);
        for(int i = 0; i < n; ++i)
            sums[i + 1] = nums[i] + sums[i];
        int ans = INT_MIN;
        deq.push_back(0);
        for(int j = 1; j <= n; ++j)
        {
            int pj = sums[j];
            int pi = sums[deq.front()];
            ans = max(ans, pj - pi);
            while(!deq.empty() && sums[deq.back()] >= pj)
                deq.pop_back();
            deq.push_back(j);
            if(j - deq.front() == n)
                deq.pop_front();
        }
        return ans;
    }
};

算法3: 分治

对于左闭右开区间 [left, right)，它的长度为 length = right - left。

令 mid = (length + 1) / 2 + left，可以得到两个左闭右开的子区间 [left, mid), [mid, right)。

[left, right) 上和最大的子串的位置有三种情况：

  1. 完全在左半区间 [left, mid) ：直接递归，需要 $O(\log N)$ 次
  2. 完全在右半区间 [mid, right)：直接递归，需要 $O(\log N)$ 次
  3. 两个半区间各占一部分：在递归的回溯阶段做，这部分需要O(N)

三种情况的最大子串和分别记为 left_result, right_result, middle_result。max(left_result, right_result, middle_result) 就是 [left, right) 上的最大子串和。递归终止条件为 length = 1。

分治法的时间复杂度为 $O(N\log N)$，不如动态规划的 O(N)，但是这种分治法还是有意义的，它可以扩展成动态询问 [i, j] 的最大子段和。

如果把分治过程中子区间的最大子段和维护在线段树上，线段树上就隐含了分治算法。那么在建好的线段树上查询区间最大子数组和就只需要考虑下面三种情况就可以了：

  1. 左子树最大子段和
  2. 右子树最大子段和
  3. 左子树的最大后缀和 + 右子树的最大前缀和

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return _maxSubArray(nums, 0, n); // [0, n)
    }

private:
    int _maxSubArray(const vector<int> &nums, int left, int right)
    {
        // [left, right)
        int length = right - left;

        // 递归终止
        if(length == 1) 
            return nums[left];

        int mid = (length + 1) / 2 + left;

        // 至少两个元素
        // 分别递归左右子区间
        int left_result = _maxSubArray(nums, left, mid);
        int right_result = _maxSubArray(nums, mid, right);

        // 横跨两个区间的候选答案 mid_result 一定包含 nums[mid] 和 nums[mid - 1]
        int right_sum = nums[mid];
        int right_maxsum = right_sum;
        for(int i = mid + 1; i < right; ++i)
        {
            right_sum += nums[i];
            right_maxsum = max(right_maxsum, right_sum);
        }
        int left_sum = nums[mid - 1];
        int left_maxsum = left_sum;
        for(int i = mid - 2; i >= left; --i)
        {
            left_sum += nums[i];
            left_maxsum = max(left_maxsum, left_sum);
        }
        int mid_result = left_maxsum + right_maxsum;

        return max(max(left_result, right_result), mid_result);
    }
};
Share