请问一个问题：带限制的连续子数组最大和 - 编程论坛

#2

rjsp2019-04-29 11:02

不知道对不对，我的算法是在“求最大连续序列和”的基础上增加了一个满m个数则从左边退部分数的动作。

程序代码：

#include <stdio.h>

long long foo( const int a[], size_t n, size_t m )
{
    long long ans = a[0];

    long long sum = a[0];
    size_t left = 0;
    for( size_t i=1; i!=n; ++i )
    {
        if( i-left < m )
        {
            if( sum<=0 || sum+a[i]<=0 )
            {
                left = i;
                sum = a[i];
            }
            else
            {
                sum += a[i];
            }
        }
        else
        {
            long long tmp_maxsum = 0;
            size_t tmp_left = i;
            long long tmp_sum =0;
            for( size_t j=i-1; j>left; --j )
            {
                tmp_sum += a[j];
                if( tmp_maxsum < tmp_sum )
                {
                    tmp_maxsum = tmp_sum;
                    tmp_left = i;
                }
            }

            sum = tmp_maxsum + a[i];
            left = tmp_left;
        }

        if( ans < sum )
            ans = sum;
    }

    return ans;
}

int main( void )
{
    size_t n, m;
    scanf( "%zu%zu", &n, &m );
    int a[100000];
    for( size_t i=0; i!=n; ++i )
        scanf( "%d", &a[i] );
    printf( "%lld\n", foo(a,n,m) );
}

#3

bytton2019-04-29 12:51

您的思路应是正确的，可这个效率不足以通过这道题唉。

#4

bytton2019-04-29 13:29

刚刚想到方法解决了。
我预处理了前缀和，然后用线段树维护前缀和的最小值。
以第i个元素为结尾的最大连续序列和就是：max( sum[i] - sum[j] ) （其中sum[j]是i的前m个元素中前缀和的最小值）
这样算法的时间复杂度是O(nlogn)的，能跑得动。

通过代码如下：

程序代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
const long long inf = 0x3f3f3f3f3f3f3f3fLL;
long long a[N], sum[N], tree[N<<2];

void pushup(int rt)
{
    tree[rt] = min(tree[rt<<1], tree[rt<<1|1]);
}

void build(int l, int r, int rt)
{
    if (l == r){
        tree[rt] = sum[l];
        return;
    }
    int mid = (l+r) >> 1;
    build(l, mid, rt<<1);
    build(mid+1, r, rt<<1|1);
    pushup(rt);
}

long long query(int L, int R, int l, int r, int rt)
{
    if (L <= l && r <= R){
        return tree[rt];
    }
    int mid = (l+r) >> 1;
    long long ans = inf;
    if (L <= mid) ans = min(ans, query(L, R, l, mid, rt<<1));
    if (R > mid) ans = min(ans, query(L, R, mid+1, r, rt<<1|1));
    return ans;
}

signed main(void)
{
    ios::sync_with_stdio(false), cin.tie(0);
    int n, m;
    long long mx = -inf;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i){
        cin >> a[i];
        mx = max(mx, a[i]);
        sum[i] = sum[i-1] + a[i];
    }
    if (mx <= 0){
        cout << mx << endl;
        return 0;
    }
    build(0, n, 1);
    long long ans = 0;
    for (int i = 1; i <= n; ++i){
        int s = (i - m >= 0) ? i-m : 0;
        ans = max(ans, sum[i]-query(s, i, 0, n, 1));
    }
    cout << ans << endl;
    return 0;
}