杭州电子科技大学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 编辑 ]