题解 | 最大连续子序列

#include<iostream>


using namespace std;
const int maxn = 10005;
int dp[maxn];
int a[maxn];
int main() {
    int n;
    while (cin >> n) {
        if (n == 0)break;
        int flag = 1;
        for (int i = 0; i < n; i++) {
            cin >> a[i];
            if (a[i] >= 0)flag = 0;
        }
        if (flag == 1) { //全为负
            cout << 0 << " " << a[0] << " " << a[n - 1] << endl;
            continue;
        }
        dp[0] = a[0];
        int maxd = dp[0], lhs = 0, rhs = 0, flagl = 0, flagr = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] > dp[i - 1] + a[i]) {
                dp[i] = a[i];
                flagl = i;
                flagr = i;
            } else {
                dp[i] = dp[i - 1] + a[i];
                flagr = i;
            }
            if (maxd < dp[i]) {
                maxd = dp[i];
                lhs = flagl;
                rhs = flagr;
            }
        }
        cout << maxd << " " << a[lhs] << " " << a[rhs] << endl;
    }
}

全部评论

相关推荐

门口唉提是地铁杀:之前b站被一个游戏demo深深的吸引了。看up主页发现是个初创公司,而且还在招人,也是一天60。二面的时候要我做一个登录验证和传输文件两个微服务,做完要我推到github仓库,还要我加上jaeger和一堆运维工具做性能测试并且面试的时候投屏演示。我傻乎乎的做完以后人家跟我说一句现在暂时不招人,1分钱没拿到全是白干
你的秋招第一场笔试是哪家
点赞 评论 收藏
分享
07-02 13:50
闽江学院 Java
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务