文章
25
粉丝
0
获赞
141
访问
4.6k
tem只记录 “当前正在尝试的子段” 的起始位置,只有当这个子段的和超过了全局最大值 maxx 时,才把 tem 的值赋给最终的 start,这样就能保证 start 始终是最大子段的真正起始位置。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n && n != 0) {
vector<long long> arr(n);
vector<long long> dp(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
dp[0] = arr[0];
long long maxx = arr[0];
int start = 0, end = 0; // 最终答案的起点终点
int tem = 0; //临时起点,只有尝试并且能更新最大段之和时才能更新
for (int j = 1; j < n; j++) {
if (dp[j - 1] + arr[j] >= arr[j]) {
...
登录后发布评论
暂无评论,来抢沙发