1007.Maximum Subsequence Sum

2017-10-29

英文描述

Maximum Subsequence Sum (25)
Given a sequence of K integers { N1, N2, …, NK }. A continuous subsequence is defined to be { Ni, Ni+1, …, Nj } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line.
In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case).
If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4

中文描述

最大子序列
提供一个K个整数的序列{ N1, N2, …, NK }。一个连续的子序列被定义为{ Ni, Ni+1, …, Nj }其中1 <= i <= j <= K。最大子序列指的是一个连续的子序列中所有的元素之和最大。举一个例子，给出一个序列{ -2, 11, -4, 13, -5, -2 }，最大子序列是{ 11, -4, 13 }，最大子序列中的和为20。
现在你要求得最大子序列的和的最大值，以及在最大子序列中第一个和最后一个数。
输入规格：
每一个输入文件包含一个测试用例。每个用例占据两行。第一行包含一个正数（K <= 10000）。第二行包含K个数，数与数直接被空格间隔。
输出规格：
每个测试用例，在一行内输出最大和以及最大子序列中第一个和最后一个数字。
这些数字必须以空格间隔，但在行末尾没有空格。在一个用例中，最大子序列不是唯一的，输出下标最小的i和j。如果K个数字都是负数，最大和被定义为0，并且你需要输出整个序列中第一个和最后一个数字。
样例输入:
10
-10 1 2 3 4 -5 -23 3 7 -21
样例输出:
10 1 4

分析与解题

我试着用暴力算法去写了这个，没想到竟然通过了，因此我在怀疑pat那些你只要能想出办法解决的，也不用太去考虑效率的事情，也就是说，你无论使用什么算法，很少会内存溢出或者时间超时。刚才去看了《算法导论》关于这个问题的出处，在第四章分治策略中出现的，刚好那是写了时间测试，暴力和分治的差别还是很大的，尤其在输入规模巨大的时候，当数据量在10w时候，分治是0.01秒，暴力是15秒。刚好这个题是1w，要求是0.4秒，我测了1w中暴力的数据基本在0.3秒和0.2秒之间，所以飘过了。
分治的策略的确是很厉害的，这里我在说一遍，分治是把这个最大数组分成2个数组，之后分别求这两个子数组中最大子序列，其实我刚看了《算法导论》中分别求子序列的算法，其实也是基于暴力的，所以我常认为暴力是基本算法，分治的策略却把他分开来算，分别求的2个数组，分治总提到关键的一点，最大子数组必然位于左或右两个数组中或者跨越了这两个数组，他只对其中跨越这两个子数组的问题进行了处理，其余的情况使用了递归进行编写，昨天通过演绎的手法对代码进行了运行，虽然比较麻烦，但也看明白了代码的运行策略。分治这玩意确实很厉害，就在这个求最大子序列的问题上，他的策略的确很牛，我刚刚讲到暴力算法是基础算法，其实并不是的，起码在这个分治算法是不是的，但终其最基本的算法是比较，比较也算不是一个算法，可以说是方案。
在此我再来谈谈分治。我还是通过演绎的方法吧，我的水平可能也归纳不来。就好比3，4，5。这个序列，分治的前提推论是最大子序列必然位于：{3}、{5}和{3，4，5}这三个子序列中，之后它开始分别求这3个子序列，因为{3}和{5}这两个子序列的求解同原问题求解相同，这也就是DP中谈到的最优子结构，因为原问题就是求某一个序列的最大子序列，所以{3}和{5}这两个子序列可以递归去求，而第三个子序列{3，4，5}，是表明，要求子序列一定是跨越了{3}和{5}这两个子序列，所以最大子序列必然位于{3，4}和{5}这两个子序列之间，这一点我感觉自己也讲不明白，我看了原文中写的是找到{3，4}和{5}这两个子序列的最大子序列之后将其合并，关键就在于这个合并，以及他在寻找{3，4}这个最大子序列时的顺序，是相当迷人的，这个问题你咋一听其实也是寻找{3，4，5}这个序列的最大子序列，但这个问题是加了前提的，前期就是最大子序列必然是跨越了左子序列{3}和右子序列{4}的，因为这个序列就是跨越了左和右的，因为左部最大子序列的值为3下标是1，1，右边最大子序列值为5下标是3，3。因此这个最大子序列是跨越了这两个子序列的，也就是在{3，4，5}这个子序列中的。啰嗦了一堆，我还是举个例子来表明，假如有这样一个子序列{1，2，-4，4，5}，这个子序列的最大子序列是在右边的，也就是{4，5}。那么这个子序列也要求的中点为3将这个序列分开的两个子序列{1，2，-4}和{4，5}这两个子序列的最大子序列，之后将其合并，其实我感觉这里的两个子序列的最大子序列是有一些歧义的，因为最大子序列有左和右的说法，这里其实是先求得左，再求得右，之后将其合并，也就是说{1，2，-4，4，5}返回的最大子序列的值是8，下标是1和5，所以这个问题的描述虽然是求得它的最大子序列，但限制的条件是跨越了中点的。
因此分治的本质和暴力的思路是不同的，暴力就是穷举，分治是先考虑问题结构，之后与子问题进行连接，之后再原问题与子问题直接找到连接的限制，再去求解问题。

C语言实现

#include<stdio.h>
int info[10001];  //sequence
int k = 10000;
int max = 0;
int first; 
int last;
int check = 0; //check为0的话，意味着全是负数
void input()
{
	scanf("%d", &k);
	int i = 1;
	while(i <= k)
	{
		scanf("%d", &info[i]);
		if(info[i] >= 0)
			check = 1;
		i++;
	}
}
void calc()
{
	int i = 1, j = 1, sum = 0;
	while(i <= k)
	{
		sum = 0;
		j = i;
		while(j <= k)
		{
			sum = sum + info[j];
			if(max < sum)
			{
				max = sum;
				first = i;
				last = j;
			}
			j++;
		}
		i++;
	}
}
int main()
{
	input();
	if(check == 0)
		printf("%d %d %d", 0, info[1], info[k]);
	else
	{
		calc();
		printf("%d %d %d", max, info[first], info[last]);
	}
	return 0;
}

测试链接

click me