第一讲习题

佚名 5年前 (2019-03-03) 算法 1971人围观抢沙发百度已收录

共三道，前两道就是前面的例题，这里记录第三道：

同样是求最大子列和，输出最大和和子列的首末元素。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

如果出现相等的子列，输出i，j最小的；如果全是负数，输出0和数列的首末元素。

判断是否全负，剩下的按照常规运算。

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int K=100000;
 5 int main(){
 6     int n,num=0,temp=0;
 7     scanf("%d",&n);
 8     int a[K],f=0,l=0;
 9     for(int i=0;i<n;i++){
10         scanf("%d",&a[i]);
           if(a[i]<0) temp++;
11     }15     int thissum=0,maxsum=0;
16     if(temp==n){
17     printf("0 %d %d\n",a[0],a[n-1]);
18     }
19    else{
22         for(int i=0;i<n;i++){
23         thissum+=a[i];
24         if(thissum>maxsum){//只有thissum>maxsum时更新l,f,保证l和f指向第一组最大值
25             maxsum=thissum;
26             l=a[i];
27             num++;
28             f=a[i-num+1];
29         }
30         else if(thissum<=maxsum&&thissum>=0){
31             num++;
32         }
33         else if(thissum<0){
34             thissum=0;
35             num=0;
36         }
37     }
38     printf("%d %d %d\n",maxsum,f,l);
39     }
40     return 0;
41 }