杭州电子科技大学 Online Judge 之 “最大连续子序列(ID1231)”解题报告
杭州电子科技大学Online Judge 之 “最大连续子序列(ID1231)”解题报告巧若拙(欢迎转载,但请注明出处:http://blog.)
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,输出整个序列的首尾元素。
Sample Input
6
-2 11 -4 13 -5 -2
10
-10 1 2 3 4 -5 -23 3 7 -21
6
5 -8 3 2 5 0
1
10
3
-1 -5 -2
3
-1 0 -2
0
Sample Output
20 11 13
10 1 4
10 3 5
10 10 10
0 -1 -2
0 0 0
算法分析:
本题是动态规划算法的典型应用。有两种方法来实现动态规划算法。
算法1:
使用变量sum累计当前连续子序列之和,只要sum>=0,就不停累计下去,并把最大连续子序列之和记录到maxSum中。如果sum小于0了,则将sum归零,重新开始。
题目要求输出该子序列的第一个和最后一个元素,我们只需要在更新maxSum的同时更新记录最大子序列边界的变量maxRight和maxLeft就行了。
为了能够正确处理序列值为非正整数的情况,我们初始化maxSum = -1;
maxLeft = 0;
maxRight = n-1;
说明:
算法思想:动态规划。
数据结构:基本数据类型。
时间复杂度: O(N);
本题的姐妹题是“MaxSum(ID1003)”,算法思想相同,输出要求不同。
12390498 2014-12-04 13:59:52 Accepted 1231
62MS 256K 878 B
C 巧若拙
算法2:
设置一个辅助数组S[MAX];用来存储连续子序列的最大和。先取S[0] = A[0]; 如果S[i-1] > 0,则S[i] = S[i-1] + A[i]; 否则S[i] = A[i]; 即重新计算S[i]的值,相当于算法1中的将sum归零。
这样遍历数组A,计算出所有S[i]。然后遍历S[i],找出最大值,即最大连续子序列和,对应的下标i就是序列的右边界right;从right往前遍历,直到S[i] < 0,则左边界left=i+1。
说明:
算法思想:动态规划。
数据结构:基本数据类型。
时间复杂度: O(N);
空间复杂度: O(MAX);
12399272 2014-12-05 14:14:37 Accepted 1231
124MS 1132K 1010 B
C 巧若拙
代码如下:
#include<stdio.h>
#include<malloc.h>
#include<math.h>
#define MAX 10000
void MaxSubsequenceSum(const int A[], int n);//动态规划算法
int main()
{
int A[MAX];
int k, i;
scanf("%d", &k);
while (k != 0)
{
for (i=0; i<k; i++)
{
scanf("%d", &A[i]);
}
MaxSubsequenceSum(A, k);//动态规划算法
scanf("%d", &k);
}
return 0;
}
void MaxSubsequenceSum(const int A[], int n)//动态规划算法
{
int sum, maxSum, i, left, maxRight, maxLeft;
maxSum = -1;
sum = 0;
maxLeft = 0;
maxRight = n-1;
for (left=i=0; i<n; i++)
{
sum += A[i];
if (sum > maxSum)
{
maxSum = sum;
maxLeft = left;
maxRight = i;
}
else if (sum < 0) //连续子序列之和小于0了,则重新开始
{
sum = 0;
left = i + 1;
}
}
if (maxSum < 0)
maxSum = 0;
printf("%d %d %d\n", maxSum, A[maxLeft], A[maxRight]);
}
算法2:
void MaxSubsequenceSum(const int A[], int n)//动态规划算法
{
int S[MAX];//用来存储连续子序列的最大和
int i, left, right;
S[0] = A[0];
for (i=1; i<n; i++)//存储各连续子序列的最大和
{
if (S[i-1] > 0)
S[i] = S[i-1] + A[i];
else
S[i] = A[i];
}
for (right=i=0; i<n; i++)//查找连续子序列的最大和的右边界
{
if (S[i] > S[right])
right = i;
}
for (i=right; i>=0; i--)//查找连续子序列的最大和的左边界
{
if (S[i] < 0)
break;
}
left = i + 1;
if (S[right] < 0)//全部元素都是负数的情形
{
left = 0;
right = n - 1;
S[right] = 0;
}
printf("%d %d %d\n", S[right], A[left], A[right]);
}
[ 本帖最后由 巧若拙 于 2014-12-5 14:56 编辑 ]