上海计算机学会2022年8月月赛C++丙组T3最大子串_最大子串 上海市计算机学会

最大子串

内存限制: 256 Mb时间限制: 1000 ms

题目描述

给定 n 个整数 a1​,a2​,⋯,an​ 构成一个序列，请为这个序列寻找一个子串，使数字之和达到最大。子串是原序列中连续且保持顺序的一段数字，空串或序列全体都算原序列的子串。

输入格式

第一行：单个整数 n。
第二行：n 个整数 a1​,a2​,…,an​。

输出格式

单个整数：表示子串的最大和。

数据范围

• 对于 30% 的数据，1≤n≤200，
• 对于 60% 的数据，1≤n≤5000，
• 对于 100% 的数据，1≤n≤200,000。
• −10000≤ai​≤10000

样例数据

输入:
5
1 2 -10 2 3
输出:
5

输入:
3
-1 -2 -3
输出:
0

输入:
3
3 -2 3
输出:
4

 解析：贪心思维，如果当前的子串和为正数，可以为后边的子串带来收益，保留，如果是负数，舍弃，从零开始，详见代码：

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main() {
    int n;
    long long sum = 0;//当前子串和
    long long ans = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
        if (sum < 0) sum = 0;//如果负数，归零
        if (sum > ans) ans = sum;//求最大值
    }
    cout << ans << endl;
    return 0;
}