算法疑难杂症

带长度限制的最大子数组和

字数统计: 1.3k字   |   阅读时长: 5分
,

摘要: 带长度限制的最大子矩阵和

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

在文章 最大子数组和的三种解法 中，我们详细拆解了最大子数组和这个问题，并且了解到这个问题有三种解法，都非常主流，并且各个方法都有它适用的变种问题。

在文章 环形数组上的最大子数组和 和文章 最大子矩阵和 中，我们看了两类最直接的变种：第一个是把数组变成环形数组，那道题的重点是怎样把环形数组上的问题转换为普通数组上的问题。只要完成了正确的转换，就可以套用普通数组上我们已经知道的解法；第二个是把数组变成矩阵，那道题的重点是怎样把二维上的问题转化为一维上的问题，只要能正确转化，就可以套用一维上的已知解法来解决。

除了【数组->矩阵】和【数组->环形数组】这类比较直接的变种，对求和的过程增加限制也是一类变种，例如在文章 带大小限制的最大子数组/子矩阵和 中，我们见到了要求子数组和不大于 k 的限制的最大子数组和的问题。

本文我们要看的是限制子数组长度不大于 m 时的最大子数组和问题。解法依然是前缀和 + 单调队列的结构，可以与限制和不大于 K 的那个问题一起看，代码非常类似。

题目

本题在 leetcode 上暂时没有，在 acwing 上有，本文给出的代码是基于 acwing 上的题目的，感兴趣的可以去提交一个。题目如下：

135. 最大子序和

输入一个长度为 n 的整数序列，从中找出一段长度不超过 m 的子数组，使得子数组中所有数的和最大。

题解

回顾: 用前缀和解决无限制的最大子数组和问题

为了对比方便，首先还是回顾一下用前缀和和单调队列算法解决无限制的最大子数组和问题的过程。

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

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

1
2
a[0..i] 的和 sums[i+1] 求出后
问 sums[0..i] 的最小值是多少

这里问最值的区间左端点是没有限制的，一直是 0，当新下标 i 来的时候，只会在队尾弹出一些比 sums[i] 小的，而不会因为区间的限制从左边弹出下标。

这种不用从左边弹出下标的场景用单调队列有点多此一举，不过对于有长度限制的最大子段和，就需要用到单调队列的从左边弹出不满足区间限制的下标这个特性了，这正是本题的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    vector<int> sums(n + 1);
    deque<int> deq;
    deq.push_back(0); // sums[0] = 0
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        sums[i + 1] = sums[i] + nums[i];
        // 此时问：sums[0..i] 上的最小值 mx 是多少
        int  mx = sums[deq.front()];
        ans = max(ans, sums[i + 1] - mx);
        while(!deq.empty() && sums[deq.back()] >= sums[i + 1])
            deq.pop_back();
        deq.push_back(i + 1);
    }
    return ans;
}

算法：前缀和+单调队列

之前我们了解到，无限制的最大子数组和问题有三种解法：动态规划、分治、前缀和+单调队列。每种方法都很主流，且各自有它适用的变种问题。

限制子数组长度就是一类前缀和+单调队列非常适合的变种问题。只需要保持单调队列中维护的下标范围始终在长度小于等于 m 的范围内即可。

1
2
a[0..i] 的和 sums[i+1] 求出后
问 sums[max(0, i - m + 1)..i] 的最小值是多少

代码(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
#include <iostream>
#include <vector>
#include <deque>
#include <climits>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> sums(n + 1);
    deque<int> deq;
    deq.push_back(0); // sums[0] = 0
    int ans = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        int v;
        cin >> v;
        sums[i + 1] = sums[i] + v;
        // 此时问: sums[max(0, i - m + 1)..i] 的最小值是多少
        int mx = sums[deq.front()];
        ans = max(ans, sums[i + 1] - mx);
        while(!deq.empty() && sums[deq.back()] >= sums[i + 1])
            deq.pop_back();
        deq.push_back(i + 1);
        // 保持 i - (deq.front() - 1) + 1 <= m
        if(i - (deq.front() - 1) + 1 > m)
            deq.pop_front();
    }
    cout << ans << endl;
}
Share