[算法竞赛进阶指南]最大子序和(前缀和+单调队列)

偏执的太偏执、 2022-04-24 07:12 169阅读 0赞

# [\[算法竞赛进阶指南\]最大子序和][Link 1] #

### Description ###

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

### Input ###

第一行两个数n,m（n,m<=300000） 第二行有n个数，要求在m个数内找到最大子序和

### Output ###

一个数，数出他们的最大子序和

### Sample Input ###

6 4
    1 -3 5 1 -2 3

### Sample Output ###

### 前缀和+单调队列 ###

这道题相当于求区间和最大，那可以考虑前缀和相减。单调队列可用于求区间最值问题。  
维护一个单调递增队列，队头元素始终是最小的，队尾元素始终是最大的。  
想想，要求两数差最大，那肯定要一个最大，一个最小，才能得到差最大，所以要维护一个单调递增队列。使入队元素与队头元素作差。

#include <iostream>
    #include <deque>
    #include <cstdio>
    #include <algorithm>
    using namespace std;
    int n, m;
    int nums[300000 + 5];
    int s[300000 + 5];
    deque<int> deq;
    int ans = 0;
    int main()
    { 
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        { 
            cin >> nums[i];
            if (i == 0)
                s[i] = nums[i];
            else
                s[i] = s[i - 1] + nums[i];
        }
        deq.push_back(0); // 保存一个初始元素0，用于比较数列的第一个元素。
        for (int i = 1; i <= n; i++)
        { 
            while (!deq.empty() && s[deq.back()] > s[i])
            {  // 抛出比入队大的队尾元素
                deq.pop_back();
            }
            deq.push_back(i);
            while (!deq.empty() && deq.front() < i - m)
            {  //抛出过期的元素
                deq.pop_front();
            }
            ans = max(ans, s[i] - s[deq.front()]);
        }
        cout << ans << endl;
        return 0;
    }

[Link 1]: http://acm.ncst.edu.cn/contest_problem.php?cid=1028&pid=3