题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=7&page=show_problem&problem=448
题意分析:
    求连续子序列的最大和,当最大和有多个时,找出长度最长的;当长度最长的有多个时,找出最先出现的那个。
题意分析:
    这是一道动态规划的典型题目。
    WA了好多次!!!纠结了很久才发现:当找出一个最大和的子序列时,如果它前面几个数之和是0,这个最大和子序列长度要加上前面那几个数。

代码如下:
#include <stdio.h>

int a[20001];

int main(){
    int T,n,max,sum,s,e,ss,len;
    int i,k;
    scanf("%d",&T);
    for(k=1; k<=T; k++){
        scanf("%d",&n);
        s = ss = 1;e = 2;
        max = 0;sum = 0;len = 0;
        for(i=1; i<n; i++){
            scanf("%d",&a[i]);
            sum += a[i];
            if(sum < 0){
                ss = i+1;
                sum = 0;
                continue;
            }
            if( sum > max || (sum == max && len<i-ss ) ){
                max = sum;
                s = ss;
                e = i+1;
                len = e-s;
            }
        }
        if ( max == 0 )
            printf("Route %d has no nice parts\n", k);
        else
            printf("The nicest part of route %d is between stops %d and %d\n", k,s,e);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。

Post Navigation