洛谷 P1115 最大子段和

// P1115 最大子段和 —— 能 AC 的那一版（O(n) 扫一遍）
//
// 递推一句话：**以第 i 个数结尾**的最大子段和，要么是「前面那一段接上 a[i]」，
// 要么是「从 a[i] 重新开始」——
//     cur = max(a[i], cur + a[i])
// 全程取最大值就是答案。
//
// ⚠ 起手值是这道题唯一的坑：`ans` 和 `cur` 都从 **a[0]** 开始，不是从 0 开始。
//   题面写的是「选出其中连续且**非空**的一段」——
//   那两个字就是这道题的全部难度（解析页第 ② 步把它量出来了）。
//
// ⚠ 用不用 long long？**这道题刚好不用**：n ≤ 2×10⁵、|aᵢ| ≤ 10⁴
//   ⇒ 和最大 2×10⁹，而 int 的上限是 2 147 483 647 —— 只差 1.47×10⁸，余量约 7%。
//   这是一道算术题，不是「保险起见都开」。（同一章的 P1908 是反过来的：差 58 倍。）

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200005;
static int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = a[0], cur = a[0];            // ★ 从 a[0] 起手，不是 0
    for (int i = 1; i < n; i++) {
        cur = max(a[i], cur + a[i]);
        ans = max(ans, cur);
    }

    cout << ans << "\n";
    return 0;
}

// P1115 ⚠ 第 ① 版：`ans` 从 0 起手 —— 教科书上最常见的写法，而它在这道题上是错的
//
// 「和变成负数就丢掉，从头再来」——这套写法本身没问题，
// 问题出在 **ans 的起手值是 0**：它等于偷偷允许了「一段都不选」。
//
// ⇒ 只要序列里**有一个非负数**，它就是对的；
//   **所有数都是负数**时，它输出 0，而正确答案是「最大的那个负数」。
//
// ★ 触发条件是一个**开关**，不是一个概率：max(a) < 0。
//   ⇒ 对拍的抓获率就等于「这一档数据里全负的比例」——
//     而那个比例是能**事先算出来**的（解析页第 ③ 步）。
//
// ★ 最小的反例只有一个数：
//     输入 `1` / `-1`  ⇒  它输出 0，正确答案 -1。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200005;
static int a[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];

    int ans = 0, cur = 0;                  // ⚠ 就是这里
    for (int i = 0; i < n; i++) {
        cur += a[i];
        if (cur > ans) ans = cur;
        if (cur < 0) cur = 0;
    }

    cout << ans << "\n";
    return 0;
}

// 数据生成器（P1115 对拍用）：`./p1115Gen <seed> [level] [n]`
//
//   level 0（默认）★ **n ≤ 10**，aᵢ ∈ [-10⁴, 10⁴] —— 抓获率能**先算出来**的那一档
//   level 1        n ≤ 200，同样的值域 —— 只把 n 放宽，抓获率就塌了
//   level 2        ★ **全是负数**（aᵢ ∈ [-10⁴, -1]）—— 触发线那一档，300/300
//   level 3        n = 1（最小的反例：`1` / `-1` 就够）
//   level 4        顶格 n（第三个参数，默认 2×10⁵）
//
// ★ 这道题的 bug 触发条件是一个**开关**：max(a) < 0。
//   ⇒ 抓获率 = 这一档里「全负」的比例，而那个比例是算术：
//     level 0 里 n 均匀取 1..10、每个数为负的概率 p = 10000/20001 ≈ 0.49998
//     ⇒ P(全负) = (1/10) Σ_{n=1..10} pⁿ ≈ **9.99%** ⇒ 300 轮期望 **29.97** 次。
//     level 1 里 n 均匀取 1..200 ⇒ 掉到约 **0.5%**（期望 1.5 次）。
//   ⇒ 这一次是**先算后量**，不是量完再解释。

#include <bits/stdc++.h>
using namespace std;
static mt19937 rng;
static int ri(int lo, int hi) { return lo + (int)(rng() % (unsigned)(hi - lo + 1)); }

int main(int argc, char** argv) {
    rng.seed((argc > 1) ? (unsigned)atoi(argv[1]) : 1);
    int level = (argc > 2) ? atoi(argv[2]) : 0;

    int n;
    if (level == 1)      n = ri(1, 200);
    else if (level == 3) n = 1;
    else if (level == 4) n = 200000;
    else                 n = ri(1, 10);
    if (argc > 3) n = atoi(argv[3]);

    printf("%d\n", n);
    for (int i = 0; i < n; i++) {
        int v = (level == 2) ? ri(-10000, -1) : ri(-10000, 10000);
        printf("%d%c", v, i + 1 == n ? '\n' : ' ');
    }
    return 0;
}

// P1115 第 ③ 版：分治 —— 本章题单点名要练的那一版
//
// 「跨越中点的那部分怎么算」才是分治题的真正内容（本章正文第 ⑧ 步）：
//
//     最大子段和 = max( 全在左边的, 全在右边的, **跨过中点的** )
//                    ↑递归           ↑递归        ↑左半边的最大后缀 + 右半边的最大前缀
//
// ⚠ 而「最大后缀 / 最大前缀」这两个量**必须非空** ——
//   它们各自至少要含一个元素，跨中点那一段才真的跨过了中点。
//   写成「允许为空（即下限 0）」就退化成 p1115DivideBad.cpp，
//   而那和第 ① 版的 `ans = 0` **是同一个 bug 的另一副身体**。
//
// 一次递归返回四个量：整段和、最大前缀、最大后缀、区间内最大子段和。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200005;
static int a[MAXN];

struct Node { long long sum, pre, suf, best; };

static Node solve(int l, int r) {
    if (l == r) return {a[l], a[l], a[l], a[l]};        // ★ 单个元素：四个量都是 a[l]
    int mid = l + (r - l) / 2;
    Node L = solve(l, mid), R = solve(mid + 1, r);
    Node c;
    c.sum  = L.sum + R.sum;
    c.pre  = max(L.pre, L.sum + R.pre);                 // 前缀：要么只在左边，要么吃掉整个左边
    c.suf  = max(R.suf, R.sum + L.suf);
    c.best = max(max(L.best, R.best), L.suf + R.pre);   // ★ 跨中点：左最大后缀 + 右最大前缀
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << solve(0, n - 1).best << "\n";
    return 0;
}

// P1115 ⚠ 第 ③' 版：分治，但「最大前缀 / 最大后缀」允许为空
//
// 和 p1115Divide.cpp 的差别只有两处 `max(0LL, …)` —— 看起来像是「顺手加个保护」。
//
// ★ 而它和第 ① 版 `ans = 0` **是同一个 bug**：
//   允许前缀 / 后缀为空 ⇒ 跨中点那一段可以是「空 + 空 = 0」⇒ 又一次偷偷允许了「不选」。
//   触发线一模一样：**所有数都是负数**。
//
// ⇒ 这一版留在这儿只为一句话：**换了实现不等于换了 bug。**
//   两处代码长得毫不相干，`p1115Zero` 是在主循环里错的、它是在合并那一步错的，
//   而它们在同一档数据上一起翻车、在别的档上一起正确 —— 逐字节相同。

#include <bits/stdc++.h>
using namespace std;

static const int MAXN = 200005;
static int a[MAXN];

struct Node { long long sum, pre, suf, best; };

static Node solve(int l, int r) {
    if (l == r) return {a[l], max(0LL, (long long)a[l]), max(0LL, (long long)a[l]), a[l]};
    int mid = l + (r - l) / 2;
    Node L = solve(l, mid), R = solve(mid + 1, r);
    Node c;
    c.sum  = L.sum + R.sum;
    c.pre  = max(0LL, max(L.pre, L.sum + R.pre));       // ⚠ 就是这个 0
    c.suf  = max(0LL, max(R.suf, R.sum + L.suf));       // ⚠ 和这个
    c.best = max(max(L.best, R.best), L.suf + R.pre);
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    for (int i = 0; i < n; i++) cin >> a[i];

    cout << solve(0, n - 1).best << "\n";
    return 0;
}

// P1115 换两把尺子：扫描 vs 分治，以及「暴力能拿多少分」这笔账
//
// 用法：./p1115Count [n]        人话版（默认 n = 2×10⁵，题面顶格）
//       ./p1115Count [n] csv    给 check:viz 用
//
// 三件事：
//   ① ★ **「分治求最大子段和是 O(n log n)」这句话，对写法有要求。**
//      每次合并都现扫一遍求最大前后缀，才是 O(n log n)；
//      像 p1115Divide.cpp 那样**把四个量一起返回**，合并就是 O(1) ——
//      一共 2n-1 次调用，总复杂度其实是 **O(n)**，和扫描版同一档。
//   ② 同一档复杂度，**常数不一样**：递归调用 + 栈 + 访存模式，实测差几倍。
//   ③ O(n²) 暴力在 40% 那一档（n ≤ 2×10³）真跑一次，再外推到顶格 ——
//      「先写个暴力拿 40 分」是一道**算术题**。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;

static const int MAXN = 200005;
static int a[MAXN];
static long long calls = 0, maxDepth = 0;

struct Node { long long sum, pre, suf, best; };
static Node solve(int l, int r, long long depth) {
    calls++;
    maxDepth = max(maxDepth, depth);
    if (l == r) return {a[l], a[l], a[l], a[l]};
    int mid = l + (r - l) / 2;
    Node L = solve(l, mid, depth + 1), R = solve(mid + 1, r, depth + 1);
    Node c;
    c.sum  = L.sum + R.sum;
    c.pre  = max(L.pre, L.sum + R.pre);
    c.suf  = max(R.suf, R.sum + L.suf);
    c.best = max(max(L.best, R.best), L.suf + R.pre);
    return c;
}

int main(int argc, char** argv) {
    int n = (argc > 1) ? atoi(argv[1]) : 200000;
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    mt19937 rng(20260827u);
    for (int i = 0; i < n; i++) a[i] = (int)(rng() % 20001u) - 10000;

    auto t0 = steady_clock::now();
    long long ansScan = a[0], cur = a[0];
    for (int i = 1; i < n; i++) { cur = max((long long)a[i], cur + a[i]); ansScan = max(ansScan, cur); }
    double msScan = duration<double, milli>(steady_clock::now() - t0).count();

    t0 = steady_clock::now();
    long long ansDiv = solve(0, n - 1, 1).best;
    double msDiv = duration<double, milli>(steady_clock::now() - t0).count();

    /* ③ O(n²) 在 40% 那一档上真跑 */
    const int NSMALL = 2000;
    static long long pre[MAXN];
    for (int i = 0; i < NSMALL; i++) pre[i + 1] = pre[i] + a[i];
    t0 = steady_clock::now();
    long long ansSq = LLONG_MIN;
    for (int i = 0; i < NSMALL; i++)
        for (int j = i; j < NSMALL; j++)
            ansSq = max(ansSq, pre[j + 1] - pre[i]);
    double msSq = duration<double, milli>(steady_clock::now() - t0).count();

    long long ansSmall = a[0], curS = a[0];          // 同一段前缀，扫描版的答案（拿来对一下）
    for (int i = 1; i < NSMALL; i++) { curS = max((long long)a[i], curS + a[i]); ansSmall = max(ansSmall, curS); }

    double sqOpsSmall = (double)NSMALL * (NSMALL + 1) / 2;
    double sqOpsFull  = (double)n * (n + 1) / 2;
    double sqSecFull  = msSq / sqOpsSmall * sqOpsFull / 1000.0;

    /* int 够不够：这道题的和最大 2×10⁵ × 10⁴ */
    long long worstSum = (long long)n * 10000;
    double headroom = (2147483647.0 - (double)worstSum) / 2147483647.0 * 100.0;

    if (csv) {
        printf("n,%d\nsame,%d\n", n, (ansScan == ansDiv) ? 1 : 0);
        printf("calls,%lld\nexpectCalls,%d\ndepth,%lld\n", calls, 2 * n - 1, maxDepth);
        printf("divSlower,%d\n", (msDiv > msScan) ? 1 : 0);
        printf("sqOk,%d\nsqFitsInSubtask,%d\n", (ansSq == ansSmall) ? 1 : 0, (msSq < 100.0) ? 1 : 0);
        printf("sqFullSecGE,%d\n", (int)sqSecFull);
        printf("worstSum,%lld\nintEnough,%d\nheadroomPct,%d\n",
               worstSum, (worstSum <= 2147483647LL) ? 1 : 0, (int)headroom);
        return 0;
    }

    printf("n = %d（题面顶格），随机数据：\n\n", n);
    printf("  扫描 O(n)      %7.2f 毫秒    n = %d 次更新\n", msScan, n);
    printf("  分治           %7.2f 毫秒    %lld 次递归调用（= 2n-1，%s），最深 %lld 层\n",
           msDiv, calls, (calls == 2LL * n - 1) ? "对上了" : "对不上", maxDepth);
    printf("  两边答案 %lld %s\n\n", ansScan, (ansScan == ansDiv) ? "一致" : "居然不一样！");
    printf("  ⇒ ★ 合并写成 O(1) 之后，分治其实也是 **O(n)** ——\n");
    printf("     「分治是 O(n log n)」说的是每次合并现扫一遍的那种写法。\n");
    printf("     同一档复杂度，分治慢 %.1f 倍：递归调用 + 栈 + 访存都要钱。\n\n", msDiv / max(0.001, msScan));
    printf("  O(n²) 暴力：n = %d（40%% 那一档）%.2f 毫秒（答案 %lld，%s）⇒ 稳过\n",
           NSMALL, msSq, ansSq, (ansSq == ansSmall) ? "和扫描版在同一段前缀上一致" : "居然不一样！");
    printf("              n = %d（顶格）按同一速率外推 **约 %.0f 秒** ⇒ 时限 1 秒，没戏\n\n", n, sqSecFull);
    printf("  ⇒ 「先写个暴力拿 40 分」不是安慰奖：部分分那一栏给的 n，\n");
    printf("     就是出题人替你算好的「暴力能跑到哪儿」。\n\n");
    printf("  顺带：和最大 %d × 10⁴ = %lld，int 上限 2147483647 ⇒ %s，余量只有 %.1f%%。\n",
           n, worstSum, (worstSum <= 2147483647LL) ? "刚好够" : "不够", headroom);
    return 0;
}