文章

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]) {
  ...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发