DP专题训练之HDU 1231 最大连续子序列-白红宇

DP专题训练之HDU 1231 最大连续子序列

阅读量：5164 次

发布时间：2019-06-13

本文共 2037 字，大约阅读时间需要 6 分钟。

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 

Hint

Hint  Huge input, scanf is recommended.

直接遍历然后不断更新下标和最大值~

//Asimple//#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define INF 0xfffffff#define mod 1000000#define swap(a,b,t) t = a, a = b, b = t#define CLS(a, v) memset(a, v, sizeof(a))#define debug(a) cout << #a << " = " << a <
                      
                        Maxsum ) { Maxsum = sum; inds = t; inde = i; } } if( Maxsum < 0 ) { printf("0 %d %d\n", a[0], a[n-1]); } else { printf("%d %d %d\n", Maxsum, a[inds], a[inde]); } }}int main(){ input(); return 0;}

加一个一模一样的题~~就只是不会出现全为负的情况~

//Asimple//#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   #include 
                   
                    #include 
                    
                     #include 
                     
                      #define INF 0xfffffff#define mod 1000000#define swap(a,b,t) t = a, a = b, b = t#define CLS(a, v) memset(a, v, sizeof(a))#define debug(a) cout << #a << " = " << a <
                      
                        Maxsum ) { Maxsum = sum; inds = t; inde = i; } } printf("Case %d:\n", k); printf("%d %d %d\n", Maxsum, inds, inde); if( k < T ) { printf("\n"); } }}int main(){ input(); return 0;}

转载于:https://www.cnblogs.com/Asimple/p/6229889.html

你可能感兴趣的文章