//https://www.codechef.com/problems/CHESUB

I wrote a recursive dp code for above question ,and then converted it into iterative dp, is there any way i can remove the third inner loop by some precomputation to optimize the code?

#include <bits/stdc++.h>
using namespace std;
using ll= long long;

vector<vector<ll>>dp;
ll pre[100011];
ll v[100011];
ll  n,k; 

ll rec(ll i, ll c){
  if(c>k)return 0;
  if(i>=n)return -1e16;
  
  if(dp[i][c]+1)return dp[i][c];
  
  ll ans=rec(i+1,c);

  for(int j=i;j<n;j++){
    ans=max(ans,c*(pre[j]-pre[i]+v[i])+rec(j+1,c+1));
  }

  return dp[i][c]= ans;
}


int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

 
 
  ll t; cin>>t;
  while(t--){
    //  dp.clear();
     cin>>n>>k;
     for(int i=0;i<n;i++){
        cin>>v[i],pre[i]=(i==0?0:pre[i-1])+v[i];      
      }

      dp=vector<vector<ll>>(n+3,vector<ll>(k+2,-1e16));

    for(int i=0;i<=n;i++){
      dp[i][k+1]=0;
    }


     for(int i=n-1;i>=0;i--){
      for(int c=k;c>=1;c--){
          dp[i][c]=dp[i+1][c];
          ll cur=-1e17;
        for(int j=i;j<n;j++){
          cur=max(cur, c*(pre[j])+dp[j+1][c+1]);
        }
          
          dp[i][c]=max(dp[i][c], cur+c*(-pre[i]+v[i]));
      }
     }

     cout<<dp[0][1]<<"\n";
    //  cout<<ans<<"\n";
  }
 }