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

题目链接

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;
}