Missing Test Case - 3077. Maximum Strength of K Disjoint Subarrays #21263
Description
LeetCode Username
CuteTN
Problem number, title, and link
- Maximum Strength of K Disjoint Subarrays https://leetcode.com/problems/maximum-strength-of-k-disjoint-subarrays/
Category of the bug
- Problem description
- Solved examples
- Problem constraints
- Problem hints
- Incorrect or missing "Related Topics"
- Incorrect test Case (Output of test case is incorrect as per the problem statement)
- Missing test Case (Incorrect/Inefficient Code getting accepted because of missing test cases)
- Editorial
- Programming language support
Description of the bug
The code below got AC but it's TLE for a specific testcase.
Language used for code
C++
Code used for Submit/Run operation
#define ll long long
class Solution {
public:
const ll INF = 1e18;
long long maximumStrength(vector<int>& nums, int k) {
int n=nums.size();
vector<vector<vector<ll>>> dp(n,vector<vector<ll>>(k+1,vector<long long>(2,-1)));
auto dfs=[&](auto&& self,int idx,int t,int flag)->ll{
if(t==0)return 0;
if(idx>=n)return -INF;
if(dp[idx][t][flag]!=-1)return dp[idx][t][flag];
ll curr = (t%2)?1:-1;
curr= curr*nums[idx]*t;
ll res=curr+self(self,idx+1,t,1);
if(!flag)res=max(res,self(self,idx+1,t,flag));
res=max(res,curr+self(self,idx+1,t-1,0));
return dp[idx][t][flag]=res;
};
return dfs(dfs,0,k,0);
}
};Expected behavior
Add a testcase base on the following JavaScript code as the actual testcase is too large:
let nums = Array(1e4).fill(-1);
let k = 99