UVA10684题解

· · 题解

题目传送门

翻译

多组数据，对于每组数据，第一行输入 n，表示元素的个数。若 n 为 0，则输入结束。接下来若干行共输入 n 个整数 a_i，表示每个元素。求 a 数组内的最大子段和 s。若 s 为非正整数，则输出 Losing streak.。若 s 为正整数，则输出 The maximum winning streak is X.，其中 X 表示 s。

思路

我的翻译里已经说明了，这题就是一道最大子段和的板子题，也是 P1115 的双倍经验。我们可以用 ans 表示目前的最优答案，用 now 表示手头正在统计的答案，说白了就是个前缀和计数器。我们可以枚举每个元素 a_i，若 now+a_i<0，说明到目前为止，前面的内容对后面来说已经完全没用了，只会连累后面，这时候我们计数器归零。若 now+a_i>0，说明迄今为止，前面的内容对后面还是有用的，这时候，我们的计数器就加上 a_i，并对 ans 取个 \max，继续运算。一路枚举到最后就行了。

代码

# include <bits/stdc++.h>
using namespace std;
int n, x, ans, now;
int main () {
    while (cin >> n, n) { //多组数据，且不知道有几组只有结束条件时可以这样写
        ans = now = 0; //多组数据要初始化
        while (n --) {
            cin >> x;
            now += x; //累加
            if (now < 0) //没用，归零
                now = 0;
            else
                ans = max (ans, now); //有用，那就取 max
        }
        if (ans > 0)
            cout << "The maximum winning streak is " << ans << ".\n";
        else
            cout << "Losing streak.\n";
    }
    return 0;
}