1 条题解
-
0
【本题解由站长编写】
求最大连续子段和,子段必须非空。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
- 上传者