当前位置:网站首页>HDU1231 最大连续子序列(分治or动规or双指针)

HDU1231 最大连续子序列(分治or动规or双指针)

2022-07-05 07:15:00 Woodenman杜

题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=1231

Question

Problem Description

给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ...,
Nj },其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个,
例如给定序列{ -2, 11, -4, 13, -5, -2 },其最大连续子序列为{ 11, -4, 13 },最大和
为20。
在今年的数据结构考卷中,要求编写程序得到最大和,现在增加一个要求,即还需要输出该
子序列的第一个和最后一个元素。

Input

测试输入包含若干测试用例,每个测试用例占2行,第1行给出正整数K( < 10000 ),第2行给出K个整数,中间用空格分隔。当K为0时,输入结束,该用例不被处理。

Output

对每个测试用例,在1行里输出最大和、最大连续子序列的第一个和最后一个元
素,中间用空格分隔。如果最大连续子序列不唯一,则输出序号i和j最小的那个(如输入样例的第2、3组)。若所有K个元素都是负数,则定义其最大和为0,输出整个序列的首尾元素。

Solve

这个题可以说非常经典了

暴力枚举左右界的做法就不说了,n^3哪哪都过不去,拿前缀和优化也不是一个好的做法。

动规

比较推荐的就是用动规、或者说双指针小模拟。但其实思路很简单

描述一下:

起初 l 和 r 都指向起点,然后 r 向右走,同时计算出 l 到 r 的和,如果加和是正数,那 r 就一直向右走,如果小于等于0,说明这一段加和不是想要的结果了(而且没有意义了),就让 l = r,重新开始计算加和,直到最后一个数被加和,期间不断更新最大和的结果 res 

待会看代码吧,这鬼话我实在是说不清楚了

分治

以前听数据结构的时候讲分治用的也是这种题,我就说一下思路,代码不搞了:

所谓分治就是不断地把一个问题拆分成多个子问题去处理

对于这道题,我们先讨论一个状态

从 l 到 r 的最大连续序列和,无非存在于 l 到 mid(mid = (l+r)/ 2) 或者 mid+1 到 r 之中,亦或者包含 mid ,左右都有,那我们就需要把三种情况的最大连续序列和都拿出来取最大值

先看左右都有的情况,怎么求呢,直接从 mid 分别向两边扩散去加和,什么时候停止呢,只能加到边界停止。

因为加了一个数和变小不代表之后不会变得比原来更大,所以只能是不断加,不断存最大值咯

再看最大连续序列和在两边的情况怎么办呢?

分治分治,分而治之,那就直接把序列拆成两半继续执行上述过程不就可以了,等拆到只剩一个元素的时候就是边界了,小于 0 的数就没有加和意义,正数就直接加上呗

伪代码写一下,因为我从来不相信自己的描述能力:

int solve(int l, int r)
{
	//拆到只有一个元素的情况 
	if(l == r){
		if(该元素 < 0) return 0;
		else return 该元素; 
	}
	
	int mid = (l + r) / 2;
	//左界最大
	int left = solve(l, mid);
	//右界最大
	int right = solve(mid + 1, r);
	
	//包含中界
	int l_num, r_num; 
	for mid to l
		l_num = max(l_num, mid到l的元素和)
	for mid to r
		r_num = max(r_num, mid到r的元素和)
	//取最大值返回 
	return max(l_num + r_num, left, right);
} 

AC Code

#include <iostream>
#include <cstring>
#include <cstdio>
#define N 10000
using namespace std;
int n, a[N+1];
int main(void)
{
	while(~scanf("%d", &n))
	{
		if(n == 0) break;	//运行结束判断 
		bool ans = false;	//全负数判别 
		for(int i = 1; i <= n; i++){
			scanf("%d", &a[i]); 
			if(a[i] >= 0) ans = true;
		}
		if(!ans){	//全为负数 
			cout <<0 <<" " <<a[1] <<" " <<a[n] <<endl;
			continue;
		}
		//结果计算 
		int l, r, resl, resr, res = -1e9, dp = 0;
		l = r = resl = resr = 1; 
		for(int i = 1; i <= n; i++){
			if(dp > 0){               //元素和大于0,直接添加元素
				dp += a[i];
				r++;
			}else{                    //元素和小于等于0,按0添加元素
				dp = a[i];
				l = r = i;            //更新左右边界
			}
			if(dp > res){
				res = dp;              //更新最大值
				resl = l; resr = r;    //更新左右界
			}
		}
		cout <<res <<" " <<a[resl] <<" " <<a[resr] <<endl;
	}
	return 0;
}

原网站

版权声明
本文为[Woodenman杜]所创,转载请带上原文链接,感谢
https://blog.csdn.net/qq_59700927/article/details/125570648