| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 984 人关注过本帖, 1 人收藏
标题:求最大子串和,杭电acm题,为什么不能通过。。。
只看楼主 加入收藏
Melody_FHM
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2011-8-26
结帖率:0
收藏(1)
已结贴  问题点数:20 回复次数:6 
求最大子串和,杭电acm题,为什么不能通过。。。
Input
The first line of the input contains an integer T(1<=T<=20) which means the number of test cases. Then T lines follow, each line starts with a number N(1<=N<=100000), then N integers followed(all the integers are between -1000 and 1000).
Output
For each test case, you should output two lines. The first line is "Case #:", # means the number of the test case. The second line contains three integers, the Max Sum in the sequence, the start position of the sub-sequence, the end position of the sub-sequence. If there are more than one result, output the first one. Output a blank line between two cases.
Sample Input
2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output
Case 1: 14 1 4
Case 2: 7 1 6

程序如下:
#include<stdio.h>
struct
{
    int max;
        int start;
        int end;
}myexp[20];
   
int main()
{
          int i;
          int j;
          int a;
          int T;
          int N;
          scanf("%d",&T);
          for(i = 0;i < T;i++)
          {
                 int sum = 0;
                 myexp[i].max = -1001;
                 int tmp = 1;
                 scanf("%d",&N);
                 for(j = 0;j < N;j++)
                 {
                          scanf("%d",&a);
                          sum = sum + a;
                          if(sum > myexp[i].max)
                          {
                                  myexp[i].max = sum;
                                  myexp[i].start = tmp;
                                  myexp[i].end = j + 1;
                          }
                          if(sum < 0)
                          {
                                  sum = 0;
                                  tmp = j + 2;
                          }
                  }
          }
                                                                                                                              
          for(i = 0;i < T;i++)
          {
                  printf("case %d:\n",i + 1);
                  printf("%d %d %d\n",myexp[i].max,myexp[i].start,myexp[i].end);
                 printf("\n");
         }
         return 0;
 }
搜索更多相关主题的帖子: position sequence between number follow 
2011-08-26 04:17
A13433758072
Rank: 11Rank: 11Rank: 11Rank: 11
来 自:广东潮州
等 级:小飞侠
威 望:1
帖 子:1182
专家分:2784
注 册:2010-7-22
收藏
得分:3 

求最大子串和,杭电ACM题,为什么不能通过。。
输入
输入的第一行包含一个整数T(1 <= T <= 20),这意味着测试用例的数量。 则T线跟进,每行的开始与数N(1 <= N <= 100000),那么N个整数后面(-1000和1000之间的所有整数)。
输出
对于每个测试用例,你应该输出两条线。 第一行是“案例:”#意味着测试用例的数量。 第二行包含三个整数,序列中最大的心,的子序列的起始位置,子序列的结束位置。 如果有多个结果,输出的第一个。 输出两起案件之间的空白行。
样例输入
2
5 6 -1 5 4 -7
7 0 6 -1 1日-6 7 -5

输出范例
案例1:14 1 4
案例二:7 1 6

一步一个脚印...............................默默地前进.....
诚邀乐于解答c菜鸟问题,的热心网友加入,  QQ群38490319
2011-08-26 04:27
相当调皮
Rank: 2
等 级:论坛游民
帖 子:7
专家分:13
注 册:2011-8-9
收藏
得分:3 
膜拜楼上的- -

芳草集女人网www.芳草集 seo学习论坛www.  www.
2011-08-26 10:13
草狼
Rank: 9Rank: 9Rank: 9
等 级:蜘蛛侠
威 望:2
帖 子:577
专家分:1040
注 册:2010-4-6
收藏
得分:3 
#include<stdio.h>
struct
{
    int max;
        int start;
        int end;
}myexp[20];

int main()
{
          int i;
          int j;
          int a;
          int T;
          int N;
          scanf("%d",&T);
          for(i = 0;i < T;i++)
          {
                 int sum = 0;
                 myexp[i].max = -1001;
                 int tmp = 1;
                 scanf("%d",&N);
                 for(j = 0;j < N;j++)
                 {
                          scanf("%d",&a);
                          sum = sum + a;
                          if(sum > myexp[i].max)
                          {
                                  myexp[i].max = sum;
                                  myexp[i].start = tmp;
                                  myexp[i].end = j + 1;
                          }
                          if(sum < 0)
                          {
                                  sum = 0;
                                  tmp = j + 2;
                          }
                  }
          }

          for(i = 0;i < T;i++)
          {
             if(i) printf("\n");
                  printf("Case %d:\n",i + 1);
                  printf("%d %d %d\n",myexp[i].max,myexp[i].start,myexp[i].end);

         }
         return 0;
}
2011-08-26 10:28
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:3 
最大连续子序列问题。
其实就是简单的DP。

倚天照海花无数,流水高山心自知。
2011-08-26 10:40
obstratiker
Rank: 8Rank: 8
等 级:蝙蝠侠
威 望:1
帖 子:198
专家分:758
注 册:2011-5-5
收藏
得分:3 
试试这个
#include<stdio.h>

int a[100]={0};
int min[10]={0};
int start[10]={0};
int end[10]={0};

int main(void)
{
    int c,m,n;
    scanf("%d",&c);
    int i,j,k,p;
    int sum;
    for(k=0;k<c;k++)
    {
        scanf("%d",&m);
        for(i=0;i<m;i++)
            scanf("%d",&a[i]);
        for(i=0;i<m;i++)
            if(a[i]<0)
                min[k]+=a[i];
        p=2;
        while(p<m)
        {
            for(i=0;i<=m-p;i++)
            {
                sum=0;
                for(j=i;j<p;j++)
                    sum+=a[j];
                if(sum>min[k])
                {
                    min[k]=sum;
                    start[k]=i+1;
                    end[k]=j;
                }
            }
            p++;
        }
    }
    for(i=0;i<c;i++)
        printf("Case %d: %d %d %d\n",i+1,min[i],start[i],end[i]);
}
2011-08-26 10:57
快速回复:求最大子串和,杭电acm题,为什么不能通过。。。
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017427 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved