当前位置：首页 > article >正文

浙大数据结构：01-复杂度2 Maximum Subsequence Sum

article 2025/3/13 22:37:15

数据结构MOOC

PTA习题

01-复杂度2 Maximum Subsequence Sum

#include <iostream>
using namespace std;
const int M = 100005;
int a[M];
int main()
{
	int k;
	cin >> k;
	int f = 1;
	for (int i = 0; i < k; i++)
	{
		cin >> a[i];
		if (a[i] >= 0)//如果出现大于0则进行在线处理
			f = 0;
	}
	if (f)
	{  //全都小于0
		cout << "0" << ' ' << a[0] << ' ' << a[k - 1];
		return 0;
	}

	int s = 0, ma = -1, l = 0, j = 0, r;
      
	for (int i = 0; i < k; i++)
	{
		s += a[i];
		if (s > ma)
		{  //更新答案
			ma = s;
			r = a[i];
			l = a[j];
		}
		if (s < 0)
		{
			s = 0;
			j = i + 1;  //因为扔掉了左边，所以答案数组的左指针一定大于i
		}
	}
	cout << ma << ' ' << l << ' ' << r;
	return 0;
}

查看全文

原文地址:https://blog.csdn.net/qq_74924951/article/details/141891335
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.kler.cn/a/291604.html 如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！