感觉可能跟LIS有关，但是我实在想不到怎么二分优化

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define PII pair<int,int>
#define tul tuple<int,int,int>
#define all(x) x.begin(),x.end()
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define lc rt<<1
#define rc rt<<1|1
const int N=3e5+6,yyx=998244353;
int n,m,k,a[N],dp[N];//前i个怪物,打了j个
vector<int> to[N];
inline void solve(){
   cin>>n;
   for(int i=1;i<=n;++i) cin>>a[i];
   int ans=0,cnt=0;
   for(int i=1;i<=n;++i){
      for(int j=i;j;--j){
        //dp[i][j]=dp[i-1][j];//放走了第i只怪物
        if(j%2==0) dp[j]=max(dp[j],dp[j-1]+2*a[i]);
        else dp[j]=max(dp[j],dp[j-1]+a[i]);
        ans=max(ans,dp[j]);
      }
   }
   cout<<ans<<endl;
}
signed main(){
  cin.tie(0)->sync_with_stdio(0);
  //freopen("D://321//in.txt","r",stdin);
  //freopen("D://321//out.txt","w",stdout);
  int _=1;
  //cin>>_;
  while(_--)
  solve();
  return 0;
}