[PAT]MaximumSubsequenceSum-最大子列和问题C语言实现

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› C++›C++教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

　　第一次写这方面的blog.自己也是初次接触相关知识,写的有不妥的地方十分欢迎大家指正~

　　这是浙大PAT上的一道算法题(据说是浙大04年研究生复试题),题目是这样的:

[PAT] Maximum Subsequence Sum

Given a sequence of $N_1N1, N_2N2, ..., N_KNK }. A continuous subsequence is defined to be { N_iNi, N_{i+1}Ni+1, ..., N_jNj } where 1 \le i \le j \le K1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.$

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer $(\le 10000≤10000). The second line containsKK numbers, separated by a space.$

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices

Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
时间限制：200ms

内存限制：64MB

代码长度限制：16kB

　　原题点击此处

　　翻译成中文就是,在程序第一行输入一个正整数N,第二行输入一个含有N个整数的序列,从中取连续的任意n个数(当然不超过N),让这n个数的和最大.接着要输出这个和的值,以及这个片段的首个和末尾数字.如果有多个连续片段的和一样大,则取下标最小的.如果全为负数,则定义其最大和为0,首个和末尾数分别是序列的首个和末尾数;

　　这个只是一个数学问题,不需要特别高深的编程技巧,所以我只说一下我的思路(文尾也会有源码).

　　既然是求连续最大和,我们首先可以肯定的说:

　　　　1.我不要负数(但不能说不要0!后面会解释).

　　　　2.我要尽可能多的连续正数.

　　根据题目要求,我们要输出头尾的数,显然我们需要一个表来保存我们输入的数.仅仅是数吗?当然不是!我们还要判断下标的大小,所以还需要保存他们的标号.于是你可能就想到了数组这种东西:直接int sequence[N]然后一个一个塞进去,简单!但这样的话,写出来的程序恐怕就是好几个for循环套來套去,然后出现O(n³)甚至O(n⁴)这种比较尴尬的事情--别忘了题目还有时间限制(200ms),我们要在各个方面都尽量加快程序的效率.首先要用指针操作代替使用数组索引(具体原因参见这里),malloc或许是一个不错的选择,但malloc出来的空间没有清零(我这个算法不清零的话,算到最后会gg..),所以改成calloc.这里还要构造一个结构体:

1 typedef struct 
2 {
3     int right_indices; //右下标
4     int left_indices;　//左下标
5     int sum;　　　　　　//当前的数
6 } cluster;

　　这个结构体除了放输入的数,还能放一个左下标,一个右下标,说白了就是题目中的那个边界.

　　接下来,我们看一看上面的sample:

　-10 1 2 3 4 -5 -23 3 7 -21

　　由上面提出的两点我们可以知道,第一个 -10 肯定是不要的, 1 到 4 肯定是"绑定"的,也就是说只要你取了第5个元素4,为了使和最大,你肯定会一直往前取到第二个元素1.这个原理同样适用于后面的 3 和 7,但是我们有没有必要去跨越中间的 -5 和 -23(这很亏啊)去接受后面的 3 和 7 呢?这里其实包含了另一个关键思路:我们之所以会取中间的负数是因为后面(或者前面)的正数能够弥补中间那些连续负数带来的损失.概括一下前面的意思就是:先合并相邻的同号再进行比较.以上sample便可转化为

10 -28 10 -21

　　很好,一目了然知道最大和是10了~(注意,所有进行过处理而形成的序列都用cluster的结构体来保存!!!!)接下来的问题是如何再程序里面实现这个功能.先请看这个部分的代码

1 int main(void)
 2 {
 3     int flag=2;//1:positive; -1:negative; 0:undefined 
 4     int K=0,i=0,temp=0,combine_count=0,n_count=0,original_count=0;
 5     int current_max=0;
 6     cluster* numbers=NULL;
 7     int* original=NULL;
 8     int final_left,final_right;
 9     scanf("%d",&K);
10     original=(int *)calloc(K+2,sizeof(int));
11     numbers=(cluster *)calloc(K+2,sizeof(cluster));

　　解释一下代码的意思:flag是一个标志变量,保存上一个数的状态,其值有 2/1/0/-1;其中2是初始状态,1为正,0为0,-1为负.temp是一个交换变量,存放当前读入的数.K是要读入的数的数量,i我就不说了.original_count为原始数据计数器.combine_count是合并后的计数器.original是一个用于保存原始数据的int数组.

　　首先我们从缓冲区一个一个读数进original:

12     for (i=0;i<K;i++)
13     {
14         scanf("%d",&temp);
15         *(original+(++original_count))=temp;

　　用++original_count是为了让用*(numbers+i)直接访问第i个数,以免出错.

16         switch (flag)
17         {
18             default:if(temp > 0) //default = 2;
19                     {
20                         numbers->sum=temp;
21                         numbers->left_indices=original_count;;
22                         flag = 1;
23                     }
24                     else if (temp < 0) n_count++;
25                     else if (temp == 0) 
26                     {
27                         numbers->left_indices=original_count;
28                         flag = 0;
29                     }
30                     break;

　　每次读入一个数据后会接着进行判断,只有在遇到第一个正数时才会写入cluster,并把标志更新为1(正数)然后更新最小下标,遇到负数会让负数计数器n_count加1,遇到0会将标志变为0,也会更新最小下标!这个很关键,因为假设输入了"0 0 0 1 2 3",那么最小下标应从第一个0算起而不是1算起(虽然他们的和都是6,但题目要求输出最小的下标!)

31                     case  1:if(temp>0) 
32                     {
33                         ((numbers+combine_count)->sum)+=temp;
34                         (numbers+combine_count)->right_indices=original_count;
35                     }
36                     else if (temp<0) 
37                     {
38                         n_count++;
39                         (numbers+combine_count)->right_indices=original_count-1;
40                         (numbers+(++combine_count))->sum=temp;
41                         flag = -1;
42                     }
43                     else if ( temp == 0)
44                     {
45                         (numbers+combine_count)->right_indices=original_count-1;
46                         flag = 0;
47                     } 
48                     break;
49             case -1:if(temp < 0) 
50                     {
51                         (numbers+combine_count)->sum+=temp;
52                         n_count++;
53                     }
54                     else if(temp == 0)
55                     {
56                         (numbers+combine_count)->left_indices=original_count;
57                     }
58                     else if (temp > 0) 
59                     {
60                         ((numbers+(++combine_count))->sum)=temp;
61                         (numbers+combine_count)->left_indices=original_count;
62                         flag=1;
63                     }
64                     break;
65             case  0:if(temp > 0) 
66                     {
67                         ((numbers+combine_count)->sum)+=temp;
68                         (numbers+combine_count)->right_indices=original_count;
69                         flag=1;
70                     }
71                     else if (temp < 0) 
72                     {
73                         n_count++;
74                     }
75                     else if ( temp == 0) ;
76                     break;

　　终于在cluster中写入第一个数了(它绝对是正数),此后的事情是这样的:

　　　　1.如果读入的数和上一个数同号(当然不考虑0啦),就把新的数加到旧的数上,如果遇到符号相反的,就让numbers指针加一,再把这个数写下去.这里又分几种情况:

　　　　　　a)正变负,会顺便更新最大下标(最后那个正数的序号写到right_indices)

　　　　　　b)负变正,会更新最小下标(正在输入的那个数的序号写到left_indices)

　　　　　　c)正变0,不更新下标!!!

　　　　　　d)负变0,更新下一个cluster的最小下标!!!(虽然等下可能又是负数)

　　　　2.如果上一个数是0.

　　　　　　e)0变正:不更新最小下标,但是要把正数写到新的cluster中

　　　　　　f)0变负:负数计数器加一

　　　　此时已经可以做第一次判断,如果负数计数器(n_count)等于输入的数的数量,则直接输出"0 0":

    if (n_count==K) 
    {
        printf("0 %d %d",*(original+1),*(original+original_count));
        return 0;
    }

　　以上便是在读入数据过程中对它们的第一步操作,这是一个动态处理过程,输入完成则处理也完成了.最后numbers结构数组中会是如下的结构(original则原封不动地保留了每一个数.):

　　"+ - + - + - + - + ..."(+代表正数,+代表负数,每个正数都含有两个下标,负数储存下标的空间是空的)

　　nice!看起来更有规律了不是吗~接下来进行下一步的处理:

　　i=0;
    while (i<=combine_count)
    {
        temp=((numbers+i)->sum)+((numbers+i+1)->sum);
        if (temp>=0)    
        {
            {
                if ((numbers+i+2)->sum != 0)
                {
                    ((numbers+i+2)->sum)+=temp;
                    ((numbers+i+2)->left_indices)=((numbers+i)->left_indices);
                }
                else if ((numbers+i+2)->sum == 0)
                {
                    ((numbers+i+2)->sum)+=temp;
                    ((numbers+i+2)->left_indices)=((numbers+i)->left_indices);
                    ((numbers+i+2)->right_indices)=((numbers+i)->right_indices);
                }
            }
            if (current_max<((numbers+i+2)->sum)) 
            {
                current_max=((numbers+i+2)->sum);
                final_left=((numbers+i+2)->left_indices);
                final_right=((numbers+i+2)->right_indices);
            }
        }
        else if (temp == 0)
        {
            ;
            
        }
        i+=2;
    }

　　我们把 "+ - + - + - + - + ..."分组为:"[+ - ][+ - ][+ - ][+ - ][+ ..."有落单也没关系,然后把每组内的正数加到负数上,正数的下标都是偶数,每次循环结尾让i加2就可以使指针对准正数.因为是正负间隔,所以一旦[+ -]中的和大于0,那么就可以将这个和再加到下一组的正数上!这样保证了跨越负数能够得到补偿!画个图就是这样:

　　[+₁ -₁ ][+₂ -₂ ][+₃ -₃ ][+₄-₄ ] -> [+₁ -₁][+_s -₂][+₃ -₃ ][+₄-₄ ] 其中+_s=(+₁ ) + (-₁ )+ (+₂)

　　如果某组内的和小于0,则将之前累积的那个正数暂时存入current_max中,然后再下一组中继续上面的累加形式,遇到小于0就拿出来与current_max比,如果大就更新current_max.当然,这个过程中会更新下标,具体的更新规则看上面的代码.这样以后,我们只遍历了一次序列,就找到了和最大且下标和最小的一串连续的数,至于他们的下标,在遍历的时候每次更新current_max就会把其对应的下标写入final_left和final_right.(取最后一次累加时下一组的正数的最大下标,取前一组和中的最小下标).

　　做到这里,基本就结束了,但是某些特殊情况会导致bug,如果输入的数据过少,则会导致即使程序遍历结束,current_max还是为0,此时就要手动将numbers第一个正数赋给current_max,此外还有一种情况会下标颠倒(映像中是最大和只有一个数的时候...?有条件的做个测试然后告诉我吧 T T).

if (current_max == 0 ) 
    {
        current_max=(numbers->sum);
        final_left=((numbers)->left_indices);
        final_right=((numbers)->right_indices);
    } 
    if (final_left>final_right) final_right=final_left;

　　之所以要单独处理这种情况另一方面也是我写的判断逻辑不够完善以至需要加两个收尾的操作...最后直接打印结果即可,有任何建议欢迎提出~(完)

P.S 下方附PTA运行结果

鲜花

握手

雷人

路过

鸡蛋

该文章已有0人参与评论

请发表评论

全部评论

专题导读

More+

10-27 六六分期app的软件客服如何联系？(六六分期

11-06 可心卡盟:win10系统火狐flash插件崩溃怎么

11-06 亲亲特价:怎么删除回收站图标

11-06 济南大学虚拟社区:鲁大师节能降温的具体办

11-06 xlueops.exe:无线网络安装向导

11-06 女斗合众国:win7系统cf与主机连接不稳定怎

11-06 0xc000022-[cf烟雾头]cf怎么调烟雾头

11-06 qizideyouhuo:应用程序无法正常启动0xc0000

11-06 ipz-185:win7系统vcf文件怎么打开

11-06 傻哥蹦迪:win10系统s4怎么打开usb调试

11-06 八神浩树gtaste:回收站清空了怎么恢复

11-06 妖尾之黑色守护:win10系统电脑没有1440x900

11-06 校园至尊魔王小说:win7系统浏览网页时字体

11-06 女斗合众国:win10系统访问共享文件夹提示请

11-06 tokyo hot n0654:恢复win7系统默认字体一招

11-06 雨酷仙境:设置win7系统转移临时文件夹腾出

11-06 阿穆纳伊之杖:win7系统开始菜单在右边还原

11-06 tunespotting:win10系统火狐flash插件总是

11-06 甘尔葛分析师：计谋网站seo关键词暴涨有什

11-06 蔡贵霖: 计谋网站seo关键词暴涨有什么秘密

11-06 博益网首页:ao3网页版进入不了解决方法

11-06 漏斗子专栏: 网站数据分析小白易懂精华篇

11-06 见证双虹怎么做:win7系统开启telnet命令的

11-06 颾狐蝶蜋:系统资源不足无法完成请求的服务

11-06 国光中学校歌:提交网站到alexa查询详细步骤

11-06 西安有情天:静态网页和动态网页的区别

11-06 红木雅尚斋:外部链接构造对网站的好处

11-06 前官礼遇：防止域名劫持–增强域安全性的10

11-06 密传二转答案: 中文分词算法有哪些

11-06 金泉家园邮编:百度快照劫持的表现及应对方

【转】如何解决C盘根目录无法创建或写入文件发布时间：2022-07-13

Codeforces1068-A/B/C/D/E-(Done)发布时间：2022-07-13

剪的笔顺,诠释剪的笔画,认识剪的部首

1 六六分期app的软件客服如何联系？(六六分期

六六分期app的软件客服如何联系？不知道吗？加qq群【895510560】即可！标题：六六分期

阅读：19182|2023-10-27

2 可心卡盟:win10系统火狐flash插件崩溃怎么

今天小编告诉大家如何处理win10系统火狐flash插件总是崩溃的问题，可能很多用户都不知

阅读：9988|2022-11-06

3 亲亲特价:怎么删除回收站图标

今天小编告诉大家如何对win10系统删除桌面回收站图标进行设置，可能很多用户都不知道

阅读：8325|2022-11-06

4 济南大学虚拟社区:鲁大师节能降温的具体办

今天小编告诉大家如何对win10系统电脑设置节能降温的设置方法，想必大家都遇到过需要

阅读：8695|2022-11-06

5 xlueops.exe:无线网络安装向导

我们在使用xp系统的过程中,经常需要对xp系统无线网络安装向导设置进行设置，可能很多

阅读：8638|2022-11-06

6 女斗合众国:win7系统cf与主机连接不稳定怎

今天小编告诉大家如何处理win7系统玩cf老是与主机连接不稳定的问题，可能很多用户都不

阅读：9655|2022-11-06

7 0xc000022-[cf烟雾头]cf怎么调烟雾头

电脑对日常生活的重要性小编就不多说了，可是一旦碰到win7系统设置cf烟雾头的问题，很

阅读：8622|2022-11-06

8 qizideyouhuo:应用程序无法正常启动0xc0000

我们在日常使用电脑的时候，有的小伙伴们可能在打开应用的时候会遇见提示应用程序无法

阅读：7998|2022-11-06

9 ipz-185:win7系统vcf文件怎么打开

今天小编告诉大家如何对win7系统打开vcf文件进行设置，可能很多用户都不知道怎么对win

阅读：8652|2022-11-06

10 傻哥蹦迪:win10系统s4怎么打开usb调试

今天小编告诉大家如何对win10系统s4开启USB调试模式进行设置，可能很多用户都不知道怎

阅读：7535|2022-11-06

客服电话

电子邮件

[PAT]MaximumSubsequenceSum-最大子列和问题C语言实现

Input Specification:

Output Specification:

Sample Input:

Sample Output:

请发表评论

全部评论

上一篇：

下一篇：

CVE-2022-24140

sussillo/hfopt-matlab: A parallel, cpu-b

emersion/go-ostatus: An OStatus library

spicetify/spicetify-cli: Commandline too

把的笔顺,知晓把的笔画,分析把的部首

剪的笔顺,诠释剪的笔画,认识剪的部首

六六分期app的软件客服如何联系？(六六分期

florent37/ViewAnimator: A fluent Android

florent37/Shrine-MaterialDesign2: implem

CVE-2020-36276

SimpleSoftwareIO/simple-sms: Send and re

关于我们

产品与服务

解决方案

139-2527-9053