C. [算法竞赛进阶指南]最大子序和

A B C D E F G H I J K L M

传统题

10000ms

128MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

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

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

Output Format

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

输入数据 1

6 4
1 -3 5 1 -2 3

输出数据 1

Hint

前缀和最大的优点就是求连续区间的值： a[10]={0,1,2,3,4,5,6,7,8,9};

b[10]={0,1,3,6,10,15,21,28,36,45}; 我们可以发现b[5]-b[2]=15-3=12=a[3]+a[4]+a[5] 这样我们就可以利用前缀和来解决这个问题

#include <iostream>
using namespace std;
#define ll long long
const int maxn = 300050;
int n, m;
int a[maxn], b[maxn];
ll sum = -0x3f3f3f;
int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = a[i - 1] + a[i];
    }
    for (int i = 0; i <= n; i++) {
        for (int j = i + 1; j <= i + m; j++)
            if (a[j] - a[i] > sum)
                sum = a[j] - a[i];
    }
    cout << sum;
    return 0;
}

Source

单调队列前缀和

NCST CCPC赛前训练1 位运算、状态压缩、快速幂、二分、差分与前缀和

未参加

状态: 已结束
规则: ACM/ICPC
题目: 13
开始于: 2019-4-8 21:00
结束于: 2019-5-10 23:59
持续时间: 771 小时
主持人: 2080226675@qq.com
参赛人数: 15

C. [算法竞赛进阶指南]最大子序和

[算法竞赛进阶指南]最大子序和

Description

Output Format

Hint

Source

NCST CCPC赛前训练1 位运算、状态压缩、快速幂、二分、差分与前缀和

状态

开发

支持

C. [算法竞赛进阶指南]最大子序和

[算法竞赛进阶指南]最大子序和

Description

Output Format

输入数据 1

输出数据 1

Hint

Source

NCST CCPC赛前训练1 位运算、状态压缩、快速幂、二分、差分与前缀和

状态

开发

支持

还没有账户？

登录