跳至正文

1 条题解

  • 0
    @ 2026-10-8 18:53:36

    【本题解由站长编写】

    求最大连续子段和,子段必须非空。Kadane 算法一遍扫完:维护 cur 表示「以当前位置结尾的最大子段和」,cur = max(a[i], cur + a[i])(要么把 a[i] 接在前面的子段后,要么自己另起一段),best 记录全程最大值。全部为负数时答案就是最大的那个负数——这正是「非空」约束的作用,初始化时 cur = best = a[0] 而非 0。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n;
        cin >> n;
        int cur = 0, best = 0;
        bool first = true;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (first) { cur = best = x; first = false; }
            else { cur = max(x, cur + x); best = max(best, cur); }
        }
        cout << best << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4161
    时间
    1000ms
    内存
    512MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者