前言

考试被\(hyj\)吊着打...

Solution

考虑一下如果前缀和如果在某一个位置的后面的任意一个前缀和都<=0，肯定这就是最大的。

然后这样子就考虑左右两边的状压dp，然后就好了。

代码实现

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;#define ll long long#define re register#define file(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)#define int llinline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int Mod=998244353;int n,a[30],sum[2000010],g[2000010],f[2000010],ans,b[2000010];int lowbit(int x){ return x&(-x);}main(){ n=gi(); for(int i=1;i<=n;++i){a[i]=gi();b[1<
           
            >j)&1)g[i]=(g[i^(1<
            
             0){ for(int j=0;j
             
              >j)&1))f[i|(1<
              
               <