01-复杂度2 Maximum Subsequence Sum (25 分)

本文主要是介绍01-复杂度2 Maximum Subsequence Sum (25 分)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

#include<iostream>
#include<algorithm>
using namespace std;

int main ()
{    int n=0,s=0,g=1;
    cin>>n;
   int a[n]={0},b[n]={0},ans[n]={0};
     for(int i=0;i<n;i++)
     {
         scanf("%d",&a[i]);
     }
     for(int i=0;i<n;i++)
     {
              b[i]=a[i];
     }
     sort(a,a+n);
     if(a[n-1]<0)
     {
              cout<<0<<" "<<b[0]<<" "<<b[n-1];
              return 0;
     }
     if(n==1)
     {
              if(b[0]>=0)
                  {
                           cout<<b[0]<<" "<<b[0]<<" "<<b[0];
                           return 0;
                  }
              if(b[0]<0)
                  {
                           cout<<0<<" "<<b[0]<<" "<<b[0];
                           return 0;
                  }
         }
       s=b[0];
     for(int i=1;i<n;i++)
     {
              if(s<0) s=0;
              int t=b[i]+s;
              ans[i]=t;
              s=t;
     }
     int aa=ans[1];
     for(int i=1;i<n;i++)
     {
         if(aa<ans[i])
         {
             aa=ans[i];
               g=i;
        }
     }
     int bb=g;
     int ss=0;
     for(int i=g;i>=0;i--)
     {
              ss=ss+b[i];
              if(ss==ans[g])        
                 {
                        bb=i;
                     break;
                 }
     }
     int hh=0;
     for(int i=bb-1;i>=0;i--)
     {
              if(b[i]==0) hh++;
              else break;
     }
  cout<<ans[g]<<" "<<b[bb-hh]<<" "<<b[g];
     return 0;
}

这篇关于01-复杂度2 Maximum Subsequence Sum (25 分)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！