复杂度估算与考场策略

// 暴力一：枚举左右端点，再老老实实把这一段加一遍 —— O(n³)
//
// 它是「一句话问题」最直白的翻译：题目说「所有连续子段里最大的那个和」，
// 那就把所有连续子段列出来，每个都算一遍和。三重循环，一个字都不多。
//
// ★ 这一章要拿它当量尺：它是四份里唯一一个「n 只能到几百」的做法。

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long best = LLONG_MIN;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            long long s = 0;
            for (int k = l; k <= r; k++) s += a[k];      // ← 每次都从头加一遍
            best = max(best, s);
        }
    cout << best << '\n';
    return 0;
}

// 暴力二：左端点固定住，右端点往右挪一格就加一个数 —— O(n²)
//
// 和 brute3.cpp 的差别只有一句：那份每次都把 a[l..r] 从头加一遍，
// 这份把上一次的和留着，`s += a[r]` 一句就接上了。
// ★ 三重循环变两重，代码却更短 —— **省掉的那一重，是重复劳动，不是必要的工作。**
//
// 这份在本章里还有第二个身份：第 10 步演示 TLE 用的就是它（n = 10⁵ 跑不完）。

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long best = LLONG_MIN;
    for (int l = 1; l <= n; l++) {
        long long s = 0;
        for (int r = l; r <= n; r++) {
            s += a[r];                                  // ← 上一次的和留着用
            best = max(best, s);
        }
    }
    cout << best << '\n';
    return 0;
}

// ★ 这一章的关键一步：把「1 秒 ≈ 10⁸ 次基本操作」这句口诀自己量出来
//
// 这句口诀几乎每本竞赛书都写，可它到底准不准、准到什么程度，没人量给你看。
// 本书的立场一向是「口诀要拿实测复核」（第 29、32、33、34、41 章各犯过一次）——
// 所以这一章不背那个数，现场量。
//
// 五个内核，每个都是「循环里做一次基本操作」，只有那一次操作不同：
//     add   x += a[i]            顺序读一个 int，加一次
//     mul   x += a[i] * a[i]     多一次乘法
//     mod   x += a[i] % 7        对**常数**取模 —— ⚠ 编译器会把它换成乘法+移位，并不是真除法
//     modv  x += a[i] % d        对**变量**取模 —— 这才是真的整数除法指令
//     rnd   x += big[j]，j 每次跳到一个伪随机位置（64 MB 的数组）—— 几乎每次都 cache miss
//
// ⇒ 五个数会差**一个数量级以上**。那正是这一章最该讲的：
//   **「10⁸」不是一个数，是一个范围，落在哪一头由「你在循环里干了什么」决定。**
//
// ⚠ 两处防编译器的写法，缺一不可（否则量到的是 0 秒）：
//   ① 每一轮的结果累加进 volatile sink —— 不然整个循环会被当成死代码删掉；
//   ② modv 的除数 d 从 argv 里来（编译期不知道），不然它和 mod 一样会被换成乘法。
//
// 用法：./ops [每个内核的目标毫秒数，默认 250] [取模的除数，默认 7] [csv]
//   带 csv 就只打 `键,每秒次数`，给 check:viz 用。

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

static const int N = 1 << 16;            // 256 KB：稳稳落在 L2 里，量的是纯计算
static const int BIG = 1 << 24;          // 64 MB：远大于任何一级缓存，量的是 cache miss
static vector<int> a, big;
static volatile long long sink = 0;

// 按显示宽度补空格：ASCII 算 1 格，汉字算 2 格（printf 的 %-Ns 数的是字节，中文列会歪）
static string padDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return s + string(max(0, width - disp), ' ');
}

/** 同上，但补在左边（右对齐用） */
static string padLeftDisp(const string& s, int width) {
    int disp = 0;
    for (unsigned char c : s) {
        if ((c & 0xC0) == 0x80) continue;
        disp += (c < 0x80) ? 1 : 2;
    }
    return string(max(0, width - disp), ' ') + s;
}

/** 跑 kernel，直到累计时间超过 targetMs，返回「每秒多少次基本操作」 */
template <class F>
double bench(F kernel, double targetMs) {
    double ms = 0;
    long long ops = 0;
    auto t0 = steady_clock::now();
    while (ms < targetMs) {
        sink += kernel();
        ops += N;
        ms = duration<double, milli>(steady_clock::now() - t0).count();
    }
    return ops / (ms / 1000.0);
}

int main(int argc, char** argv) {
    double targetMs = (argc > 1) ? atof(argv[1]) : 250.0;
    int d = (argc > 2) ? atoi(argv[2]) : 7;      // ← 编译期不知道它是 7
    bool csv = (argc > 3 && string(argv[3]) == "csv");
    if (targetMs < 1) targetMs = 1;
    if (d < 2) d = 2;

    a.resize(N);
    for (int i = 0; i < N; i++) a[i] = (i * 37) % 1000 + 1;
    big.assign(BIG, 1);
    for (int i = 0; i < BIG; i++) big[i] = (i * 7) % 1000 + 1;

    double vAdd = bench([&] {
        long long x = 0;
        for (int i = 0; i < N; i++) x += a[i];
        return x;
    }, targetMs);

    double vMul = bench([&] {
        long long x = 0;
        for (int i = 0; i < N; i++) x += (long long)a[i] * a[i];
        return x;
    }, targetMs);

    double vMod = bench([&] {
        long long x = 0;
        for (int i = 0; i < N; i++) x += a[i] % 7;
        return x;
    }, targetMs);

    double vModV = bench([&] {
        long long x = 0;
        for (int i = 0; i < N; i++) x += a[i] % d;
        return x;
    }, targetMs);

    unsigned j = 1;
    double vRnd = bench([&] {
        long long x = 0;
        for (int i = 0; i < N; i++) {
            j = j * 1103515245u + 12345u;
            x += big[(j >> 4) & (BIG - 1)];
        }
        return x;
    }, targetMs);

    const char* name[5] = { "add   x += a[i]", "mul   x += a[i]*a[i]",
                            "mod   x += a[i] % 7", "modv  x += a[i] % d",
                            "rnd   x += big[j] (j 乱跳)" };
    double v[5] = { vAdd, vMul, vMod, vModV, vRnd };

    if (csv) {
        const char* key[5] = { "add", "mul", "mod", "modv", "rnd" };
        for (int k = 0; k < 5; k++) printf("%s,%.4e\n", key[k], v[k]);
        return 0;
    }

    printf("一秒钟能做多少次？（本机实测，每个内核跑约 %.0f 毫秒）\n\n", targetMs);
    printf("%s %s %s %s\n", padDisp("内核", 30).c_str(), padLeftDisp("次/秒", 14).c_str(),
           padLeftDisp("相当于", 11).c_str(), padLeftDisp("比 rnd 快", 12).c_str());
    for (int k = 0; k < 5; k++) {
        printf("%s %14.2e %8.1f 亿 %9.1f 倍\n", padDisp(name[k], 30).c_str(),
               v[k], v[k] / 1e8, v[k] / vRnd);
    }
    printf("\n★ 最快的那行是最慢的 %.0f 倍 —— 「1 秒 ≈ 10^8 次」这句口诀，", vAdd / vRnd);
    printf("说的是这个区间里的某一处，不是一个准数。\n");
    printf("⚠ 秒数换台机器就变；**倍数**才是这张表要你记住的东西。\n");
    return 0;
}

// 正解：一遍扫过去，O(n)
//
// 这一章的主角不是这个算法本身（第 21 章那条「以 i 结尾」的递推你已经见过），
// 而是它和另外三份做法**摆在一起**的样子：四份的答案逐字节相同，
// 差别全在「n 大到什么程度还跑得完」。
//
// 递推那一句只有一个决定：
//     以 a[i] 结尾的最大子段和 cur = max(a[i], cur + a[i])
//                                    ↑ 从我自己重新开始   ↑ 接在前面那一段后面
// ⚠ 两个初值都必须是 a[1]，不是 0 —— 子段**非空**，全是负数时答案就是最大的那个负数。
//   这一处正是本章 wrongZero.cpp 的全部内容，而第一个样例挡不住它。

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);                 // 1 基下标：a[1..n]
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long best = a[1], cur = a[1];          // ⚠ 不是 0
    for (int i = 2; i <= n; i++) {
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    cout << best << '\n';
    return 0;
}

// 换一把尺子：数「基本操作」做了多少次
//
// 秒表能告诉你「这台机器上要跑多久」，但它换台机器就变。**次数不变。**
// 所以这一章的主表用的是次数，秒数只在需要「量级感」的地方出现。
//
// ⚠ 这里的次数全是**真数出来的**（在算法里放计数器），不是套公式印出来的 ——
//   然后再和公式对一遍。两者对不上，说明我对自己写的代码理解错了。
//
// 数的是同一件事：**「往和里加一个数」这个动作做了几次**。四份做法都有它，才可比。
//     O(n³)     s += a[k]        n(n+1)(n+2)/6 次
//     O(n²)     s += a[r]        n(n+1)/2 次
//     O(n log n) 跨中线那两个 for  n 是 2 的幂时正好 n·log₂n 次
//     O(n)      cur + a[i]       n−1 次
//
// 用法：./count            打一张人看的表（n = 8 / 50 / 200 / 1000）
//       ./count <n>        只打这一个 n
//       ./count <n> csv    只打 `键,值`，给 check:viz 用
// ⚠ n > 3000 时 O(n³) 那一列不真跑（真跑要几十秒），打 -1 —— 这一章正文里那一列
//   到 n = 1000 为止，再往上是**按公式外推**的，而正文会把这句话写出来。

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

static long long c3, c2, cdc, cf;

/** 一份固定的数据 —— 这四个计数和数据长什么样无关（循环边界都不看数值），所以随便造 */
static vector<long long> mk(int n) {
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) a[i] = (i % 7) - 3;
    return a;
}

void run3(const vector<long long>& a, int n) {
    long long best = LLONG_MIN;
    for (int l = 1; l <= n; l++)
        for (int r = l; r <= n; r++) {
            long long s = 0;
            for (int k = l; k <= r; k++) { s += a[k]; c3++; }
            best = max(best, s);
        }
    (void)best;
}

void run2(const vector<long long>& a, int n) {
    long long best = LLONG_MIN;
    for (int l = 1; l <= n; l++) {
        long long s = 0;
        for (int r = l; r <= n; r++) { s += a[r]; c2++; best = max(best, s); }
    }
    (void)best;
}

long long runDc(const vector<long long>& a, int l, int r) {
    if (l == r) return a[l];
    int mid = (l + r) / 2;
    long long best = max(runDc(a, l, mid), runDc(a, mid + 1, r));
    long long s = 0, lb = LLONG_MIN;
    for (int i = mid; i >= l; i--) { s += a[i]; cdc++; lb = max(lb, s); }
    s = 0;
    long long rb = LLONG_MIN;
    for (int i = mid + 1; i <= r; i++) { s += a[i]; cdc++; rb = max(rb, s); }
    return max(best, lb + rb);
}

void runFast(const vector<long long>& a, int n) {
    long long best = a[1], cur = a[1];
    for (int i = 2; i <= n; i++) { cur = max(a[i], cur + a[i]); cf++; best = max(best, cur); }
    (void)best;
}

/** 这一行的四个数；c3 在 n 太大时不真跑 */
static void measure(int n) {
    c3 = c2 = cdc = cf = 0;
    vector<long long> a = mk(n);
    if (n <= 3000) run3(a, n); else c3 = -1;
    run2(a, n);
    runDc(a, 1, n);
    runFast(a, n);
}

int main(int argc, char** argv) {
    bool csv = (argc > 2 && string(argv[2]) == "csv");

    if (argc > 1) {
        int n = atoi(argv[1]);
        if (n < 1) n = 1;
        measure(n);
        long long f3 = (long long)n * (n + 1) * (n + 2) / 6;
        long long f2 = (long long)n * (n + 1) / 2;
        long long fpow = -1;
        if ((n & (n - 1)) == 0) { int k = 0; while ((1 << k) < n) k++; fpow = (long long)n * k; }
        if (csv) {
            printf("b3,%lld\nb2,%lld\ndc,%lld\nfast,%lld\n", c3, c2, cdc, cf);
            printf("b3f,%lld\nb2f,%lld\ndcpow,%lld\nfastf,%d\n", f3, f2, fpow, n - 1);
        } else {
            printf("n = %d\n", n);
            printf("  O(n^3)     %15lld   公式 n(n+1)(n+2)/6 = %lld\n", c3, f3);
            printf("  O(n^2)     %15lld   公式 n(n+1)/2      = %lld\n", c2, f2);
            printf("  O(n log n) %15lld   n 是 2 的幂时 = n*log2(n) = %lld\n", cdc, fpow);
            printf("  O(n)       %15lld   公式 n-1           = %d\n", cf, n - 1);
        }
        return 0;
    }

    printf("「往和里加一个数」这个动作，各做了多少次\n\n");
    printf("%8s %16s %14s %12s %8s\n", "n", "O(n^3)", "O(n^2)", "O(n log n)", "O(n)");
    for (int n : {8, 50, 200, 1000}) {
        measure(n);
        printf("%8d %16lld %14lld %12lld %8lld\n", n, c3, c2, cdc, cf);
    }
    printf("\n每一列都和公式逐个对过：n(n+1)(n+2)/6 · n(n+1)/2 · (n=2^k 时 n*log2 n) · n-1\n");
    printf("★ 注意最右边两列：n 翻 5 倍，O(n) 那列就翻 5 倍，O(n^3) 那列翻 125 倍。\n");
    return 0;
}

// 读入优化：同样是读 10⁶ 个整数，四种写法差多少
//
// ★ 这一节顺带还一笔账：`ios::sync_with_stdio(false)` 在全书 283 份代码里出现过，
//   而正文**一次都没解释过它是干什么的**。这里解释清楚，并且量给你看。
//
//   cin（默认）    —— C++ 的流和 C 的 stdio 默认是**同步**的：每读一个字符都要经过
//                     stdio 那一层，还要保证两边的缓冲不打架。慢就慢在这个「同步」上。
//   cin + 关同步   —— 一句 ios::sync_with_stdio(false) 断开那层同步，cin 用自己的缓冲。
//                     ⚠ 代价：从此不许再和 scanf/printf 混用（第 26 章踩过：输出顺序会乱）。
//   scanf          —— 直接走 stdio，没有 C++ 流那层包装。
//   快读           —— 自己拿 fread 把整块字节读进来，手动拼数字。没有任何格式解析的开销。
//
// ⚠ 这四趟必须按这个顺序跑，不能换：关掉同步之后 cin 会自己预读一大块，
//   那之后再 freopen 换文件，cin 缓冲里剩的就是上一份文件的残渣。
//   ⇒ 所以「同步开着」那一趟必须排在最前面。这条坑写在这儿，免得后来的人重排一次。
//
// 用法：./read [n] [csv]     默认 n = 1000000；带 csv 就只打 `键,毫秒`，给 check:viz 用
//   它自己造数据、自己写进一个临时文件、再 freopen 回 stdin 读四遍 —— 不需要喂输入。

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

static char path[64];

static void makeData(int n) {
    snprintf(path, sizeof(path), "/tmp/read-bench-%d.txt", (int)getpid());
    FILE* f = fopen(path, "w");
    if (!f) { fprintf(stderr, "写不出临时文件 %s\n", path); exit(1); }
    mt19937 rng(20260825u);
    fprintf(f, "%d\n", n);
    for (int i = 0; i < n; i++) fprintf(f, "%d%c", (int)(rng() % 1000000000u), i + 1 == n ? '\n' : ' ');
    fclose(f);
}

/** 每一趟都从头 freopen 一次，读到的和是防作弊用的：四趟必须一模一样 */
static void reopen() {
    if (!freopen(path, "r", stdin)) { fprintf(stderr, "读不回临时文件\n"); exit(1); }
}

static int readIntFast() {                     // 手写快读：只认非负整数和负号
    static char buf[1 << 16];
    static size_t len = 0, pos = 0;
    auto gc = [&]() -> int {
        if (pos == len) { len = fread(buf, 1, sizeof(buf), stdin); pos = 0; if (!len) return -1; }
        return buf[pos++];
    };
    int c = gc();
    while (c != -1 && (c < '0' || c > '9') && c != '-') c = gc();
    int sgn = 1;
    if (c == '-') { sgn = -1; c = gc(); }
    long long x = 0;
    while (c >= '0' && c <= '9') { x = x * 10 + (c - '0'); c = gc(); }
    return (int)(sgn * x);
}

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

    double ms[4];
    long long sum[4];

    /* ① cin，同步开着（默认）—— ⚠ 必须第一个跑，见文件头 */
    { reopen();
      auto t0 = steady_clock::now();
      int m, x; long long s = 0;
      cin >> m;
      for (int i = 0; i < m; i++) { cin >> x; s += x; }
      ms[0] = duration<double, milli>(steady_clock::now() - t0).count(); sum[0] = s; }

    /* ② cin + ios::sync_with_stdio(false) */
    { reopen();
      auto t0 = steady_clock::now();
      ios::sync_with_stdio(false);
      cin.tie(nullptr);
      int m, x; long long s = 0;
      cin >> m;
      for (int i = 0; i < m; i++) { cin >> x; s += x; }
      ms[1] = duration<double, milli>(steady_clock::now() - t0).count(); sum[1] = s; }

    /* ③ scanf */
    { reopen();
      auto t0 = steady_clock::now();
      int m, x; long long s = 0;
      if (scanf("%d", &m) != 1) m = 0;
      for (int i = 0; i < m; i++) { if (scanf("%d", &x) != 1) break; s += x; }
      ms[2] = duration<double, milli>(steady_clock::now() - t0).count(); sum[2] = s; }

    /* ④ 手写快读（fread 整块读进来） */
    { reopen();
      auto t0 = steady_clock::now();
      int m = readIntFast(); long long s = 0;
      for (int i = 0; i < m; i++) s += readIntFast();
      ms[3] = duration<double, milli>(steady_clock::now() - t0).count(); sum[3] = s; }

    remove(path);

    const char* name[4] = { "cin（默认，同步开着）", "cin + sync_with_stdio(false)", "scanf", "手写快读（fread）" };
    bool same = (sum[0] == sum[1] && sum[1] == sum[2] && sum[2] == sum[3]);

    auto disp = [](const string& t) {
        int d = 0;
        for (unsigned char c : t) { if ((c & 0xC0) == 0x80) continue; d += (c < 0x80) ? 1 : 2; }
        return d;
    };
    auto padR = [&](const string& t, int w) { return t + string(max(0, w - disp(t)), ' '); };
    auto padL = [&](const string& t, int w) { return string(max(0, w - disp(t)), ' ') + t; };

    if (csv) {
        const char* key[4] = { "cin", "nosync", "scanf", "fast" };
        for (int k = 0; k < 4; k++) printf("%s,%.3f\n", key[k], ms[k]);
        printf("same,%d\nsum,%lld\n", same ? 1 : 0, sum[0]);
        return 0;
    }

    printf("读 %d 个整数，四种写法（本机实测）\n\n", n);
    printf("  %s %s %s\n", padR("写法", 30).c_str(), padL("毫秒", 8).c_str(),
           padL("比最快的慢", 15).c_str());
    double best = *min_element(ms, ms + 4);
    for (int k = 0; k < 4; k++)
        printf("  %s %8.1f %13.1f 倍\n", padR(name[k], 30).c_str(), ms[k], ms[k] / best);
    printf("\n四趟读到的和%s（%lld）—— 这一行是防作弊的：读法能换，读到的东西不能变。\n",
           same ? "完全一致" : "居然不一样，有 bug", sum[0]);
    printf("⚠ 秒数换台机器就变，**倍数**才是要记住的东西。\n");
    return 0;
}

// MLE（Memory Limit Exceeded）：数组开多大才算大
//
// ⚠ 这一份**在本机是跑得完的**（开发机内存足够），它演示的不是「崩给你看」，
//   而是**把峰值内存量出来**，再和题目给的限制比一比 —— 考场上你要做的正是这件事。
//
// 常见题目的内存限制是 256 MB。换算：
//     int    4 字节  →  256 MB 能放 6700 万个
//     long long 8 字节 → 3350 万个
//     ⚠ bool 是 1 字节，不是 1 位；vector<bool> 才是 1 位（那是个特例，第 35 章提过）
//
// 下面这个数组是 10⁸ 个 int = 4×10⁸ 字节 = **381 MiB**，超了。
// ⚠ 顺带说清一个总被搞混的换算：题目写的「256 MB」是 256 MiB = 268 435 456 字节。而它在本机能跑完这件事本身就是个陷阱：
// **本机跑得过 ≠ 评测机跑得过。**
//
// ★ 估内存和估时间是同一件事：先算一遍，再动手，别等评测机告诉你。

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

static int a[100000000];                        // 10^8 个 int = 400 MB

/** 从 /proc/self/status 里读峰值内存（VmHWM，单位 KB）—— Linux 上最直接的量法 */
static long long peakKb() {
    FILE* f = fopen("/proc/self/status", "r");
    if (!f) return -1;
    char line[256];
    long long kb = -1;
    while (fgets(line, sizeof(line), f))
        if (strncmp(line, "VmHWM:", 6) == 0) { sscanf(line + 6, "%lld", &kb); break; }
    fclose(f);
    return kb;
}

int main() {
    printf("数组声明：int a[100000000]  ->  %.0f MiB（%zu 字节）\n", sizeof(a) / 1048576.0, sizeof(a));
    printf("声明完但还没碰它，此刻峰值内存 %.1f MiB —— ★ 注意它还很小\n", peakKb() / 1024.0);

    // ⚠ 写完之后必须再读回来用掉，否则 -O2 会把这个循环整个删掉（写了没人看 = 死代码），
    //   峰值内存一点都不涨 —— 第一版就栽在这儿，量出来还是 4 MB。
    long long sum = 0;
    for (int i = 0; i < 100000000; i += 1024) a[i] = i;   // 每一页碰一下，逼系统真给内存
    for (int i = 0; i < 100000000; i += 1024) sum += a[i];
    printf("每一页都碰过一遍之后，峰值内存 %.1f MiB（校验和 %lld，防止这段被优化掉）\n",
           peakKb() / 1024.0, sum);

    printf("\n★ 两个数字差这么多，是因为系统「用到了才给」：\n");
    printf("  声明一个大数组不花内存，**碰它**才花。⚠ 但评测机量的是峰值，你迟早会碰到它。\n");
    printf("⇒ 256 MiB 的限制下，这个数组是 MLE；改成 int a[60000000]（229 MiB）才放得下。\n");
    return 0;
}

// RE（Runtime Error）：三种最常见的死法，每一种都真的会死
//
// 在输入框里填 div / at / deep 之一（默认 at），按运行看它到底怎么崩的。
//
//   div   除以 0        —— 整数除零在 x86 上是硬件异常，进程收到 SIGFPE 当场没
//   at    下标越界      —— 这里用 vector::at，它会抛异常；⚠ 写成 v[i] 的话**多半不会崩**，
//                          而是安静地读到一块不属于你的内存 —— 那就变成一个查不出来的 WA
//   deep  递归太深      —— 每一层递归都要占栈，栈只有 8 MB，压爆了就是 SIGSEGV
//
// ★ 这三种在评测机上都显示 RE，可查起来的难度完全不同：
//   前两种当场就能定位，第三种（爆栈）在小数据上一切正常，只有大数据才崩 ——
//   第 30 章那条「图上 DFS 的深度上限是点数，不是层数」讲的就是它。

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

static int lim = 100000000;                     // 递归的层数上限，从输入里来 —— 编译期不知道它多大

// ⚠ 这个函数的写法有两处是**故意**的，不然编译器会把它优化成一个循环，压根不爆栈：
//   ① 出口条件 k >= lim 里的 lim 是运行时才知道的（写死成常数的话 -Wall 直接报「无限递归」）；
//   ② 递归**返回之后**还要用本帧的 pad —— 这样它就不是尾调用，每一层都必须留一个真的栈帧。
// ★ 这本身就是一课：你以为写下的递归，编译器可能根本没那么执行。
int deep(int k) {
    volatile int pad[256];                      // 让每一层占掉约 1 KB 栈，快点压爆
    for (int i = 0; i < 4; i++) pad[i] = k + i;
    int r = (k >= lim) ? 0 : deep(k + 1);
    return r + pad[0] + pad[3];
}

int main() {
    string mode;
    if (!(cin >> mode)) mode = "at";

    if (mode == "div") {
        int a = 10, b = 0;
        cin >> b;                               // 从输入里读 b（读不到就还是 0），免得编译器直接算出来
        printf("准备算 %d / %d …\n", a, b);
        fflush(stdout);
        printf("%d\n", a / b);                  // ⚠ 就是这里
    } else if (mode == "deep") {
        printf("开始往下递归，栈只有 8 MB（每层约 1 KB，也就是八千层左右）…\n");
        fflush(stdout);
        printf("%d\n", deep(1));                // ⚠ 爆栈
    } else {
        vector<int> v(10, 7);
        int idx = 1000000;
        cin >> idx;                             // 下标从输入里来（读不到就用 1000000）
        printf("v 的长度是 %d，现在去读 v.at(%d) …\n", (int)v.size(), idx);
        fflush(stdout);
        printf("%d\n", v.at(idx));              // ⚠ 越界，抛 std::out_of_range
    }
    printf("（如果你看到这一行，说明它没崩 —— 那才是坏消息）\n");
    return 0;
}

// 正解：一遍扫过去，O(n)
//
// 这一章的主角不是这个算法本身（第 21 章那条「以 i 结尾」的递推你已经见过），
// 而是它和另外三份做法**摆在一起**的样子：四份的答案逐字节相同，
// 差别全在「n 大到什么程度还跑得完」。
//
// 递推那一句只有一个决定：
//     以 a[i] 结尾的最大子段和 cur = max(a[i], cur + a[i])
//                                    ↑ 从我自己重新开始   ↑ 接在前面那一段后面
// ⚠ 两个初值都必须是 a[1]，不是 0 —— 子段**非空**，全是负数时答案就是最大的那个负数。
//   这一处正是本章 wrongZero.cpp 的全部内容，而第一个样例挡不住它。

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);                 // 1 基下标：a[1..n]
    for (int i = 1; i <= n; i++) cin >> a[i];

    long long best = a[1], cur = a[1];          // ⚠ 不是 0
    for (int i = 2; i <= n; i++) {
        cur = max(a[i], cur + a[i]);
        best = max(best, cur);
    }
    cout << best << '\n';
    return 0;
}

// 骗分：一份**不会正解**的程序，在考场上能拿多少分
//
// ⚠⚠ 先把话说清楚：**这是考场策略，不是学习方法。**
//   平时练习时写这种东西，等于骗自己 —— 你要学的正是它跳过的那一步。
//   它只在一种场合有意义：考场上时间不够了，而这道题的部分分就摆在那儿。
//
// 它只做三件事，每一件都对应题面里的一句话：
//   ① 「所有 a[i] > 0」这一档（特殊性质分）  → 答案就是整段的和，一行搞定
//   ② 「n ≤ 1000」这几档（小数据分）        → O(n²) 的暴力足够快
//   ③ 其它                                  → ★ 兜底：输出最大的那个单个元素
//                                              它不保证对，但**一定是某个合法子段的和**，
//                                              比空着不输出强（空着一定是 0 分）
//
// ★ 第 11 步会拿它去跑五档数据，看看到底得几分 —— 结果比多数人想的高。

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

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

    int n;
    cin >> n;
    vector<long long> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    bool allPos = true;
    long long total = 0, mx = a[1];
    for (int i = 1; i <= n; i++) {
        if (a[i] <= 0) allPos = false;
        total += a[i];
        mx = max(mx, a[i]);
    }

    if (allPos) { cout << total << '\n'; return 0; }            // ① 特殊性质

    if (n <= 1000) {                                            // ② 小数据
        long long best = LLONG_MIN;
        for (int l = 1; l <= n; l++) {
            long long s = 0;
            for (int r = l; r <= n; r++) { s += a[r]; best = max(best, s); }
        }
        cout << best << '\n';
        return 0;
    }

    cout << mx << '\n';                                         // ③ 兜底
    return 0;
}