题目

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

题解

曾经做过>类似的题目<
两种思路：

• 动态规划(这个专题要求的)
• 递归与分治(类似的题目使用的方法)

先测试之前的代码,可以AC
换用动态规划

思路是:对于某一个值,可以选择将它加入到子序列里,或者选择从它开始一个新的子序列
也即**dp[i] = max(dp[i-1]+a[i] , a[i])**

然后查找dp中最大的值即可

其实我觉得处理起始和末尾才是最难的

末尾就是找到dp中最大值对应的下标指向的序列中的数字
起始需要从末尾开始往前倒推

代码

动态规划

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int INF = 0x7FFFFFFF;

const int maxn = 10005;
int dp[maxn];
int a[maxn];

bool Do() {
    int n;
    scanf("%d",&n);
    if(n == 0)
        return false;

    memset(dp,0,sizeof(dp));

    for(int i = 1;i <= n;i++) {
        scanf("%d",&a[i]);
        dp[i] = max(dp[i - 1] + a[i],a[i]);
    }


    int begin,end = a[1],Max = dp[1],pos=1;
    for(int i = 1;i <= n;i++) {
        if(dp[i] > Max) {
            Max = dp[i];
            end = a[i];
            pos = i;
        }
    }
    int sum = 0;
    begin = a[pos];
    for(int i = pos;i > 0;i--) {
        if(Max > sum) {
            sum += a[i];
            begin = a[i];
        } else {
            break;
        }
    }
    if(Max >= 0)
        printf("%d %d %d\n",Max,begin,end);
    else
        printf("%d %d %d\n",0,a[1],a[n]);
    return true;
}

int main() {

    while(Do());
    return 0;
}

递归与分治

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <functional>
using namespace std;

const int maxn = 100005;
//const int INF = (1 << 31) - 1;
const int INF = 0x7fffffff;

int a[maxn];

int dfs(int *a,int l,int r,int &begin,int &end) {
    if(l == r) {
        begin = end = l;
        return a[l];
    }
    if(l > r) {

        begin = end = -1;
        return -INF;
    }



    int mid = (l + r) / 2;
    int Max;
    int ans;
    int tbegin,tend;
    begin = end = mid;


    //中间
    int i;

    ans = 0;
    int maxl = 0;
    for(i = mid - 1;i >= l;i--) {
        ans += a[i];
        if(ans >= maxl) {
            maxl = ans;
            begin = i;
        }
    }

    ans = 0;
    int maxr = 0;
    for(i = mid + 1;i <= r;i++) {
        ans += a[i];
        if(ans > maxr) {
            maxr = ans;
            end = i;
        }

    }


    Max = maxl + a[mid] + maxr;


    //左侧
    ans = dfs(a,l,mid - 1,tbegin,tend);
    if(ans >= Max) {
        Max = ans;
        begin = tbegin;
        end = tend;
    }


    //右侧
    ans = dfs(a,mid + 1,r,tbegin,tend);
    if(ans > Max) {
        Max = ans;
        begin = tbegin;
        end = tend;
    }

    return Max;
}


bool Do() {
    int n,l,r;
    scanf("%d",&n);
    if(n== 0)
        return false;

    for(int i = 1;i <= n;i++)
        scanf("%d",&a[i]);

    int ans = dfs(a,1,n,l,r);

    if(ans >= 0)
        printf("%d %d %d\n",ans,a[l],a[r]);
    else
        printf("%d %d %d\n",0,a[1],a[n]);

    return true;
}

int main() {

    while(Do());
    return 0;
}