I was solving a lC question which is this and the code I wrote is as follows:
class Solution {
public:
int gensubsets(vector<int> &cur,vector<int> &nums, int i,int k,int cursame,int &ans,vector<vector<vector<int>>> &dp){
cout << "Current index: " << i << ", cursame: " << cursame << ", cur: ";
for (int num : cur) {
cout << num << " ";
}
cout << endl;
if(i == nums.size()){
if(cursame <= k){
ans = max(ans,static_cast<int>(cur.size()));
}
dp[cur.size()][i][cursame] = ans;
return ans;
}
if(dp[cur.size()][i][cursame] != -1) return dp[cur.size()][i][cursame];
int take = 0;
if(cur.size() >=1 && cur.back() != nums[i]){
cur.push_back(nums[i]);
take = gensubsets(cur,nums,i+1,k,cursame+1,ans,dp);
dp[cur.size()][i+1][cursame+1] = take;
// cur.pop_back();
// nottake = gensubsets(cur,nums,i+1,k,cursame,ans,dp);
}
else{
cur.push_back(nums[i]);
take = gensubsets(cur,nums,i+1,k,cursame,ans,dp);
dp[cur.size()][i+1][cursame] = take;
// cur.pop_back();
// nottake = gensubsets(cur,nums,i+1,k,cursame,ans,dp);
}
cur.pop_back();
int nottake = gensubsets(cur,nums,i+1,k,cursame,ans,dp);
// dp[cur.size()][i][cursame] = max(take,nottake);
return dp[cur.size()][i][cursame] = max(nottake,take);
}
int maximumLength(vector<int>& nums, int k) {
int ans = 0;
vector<int> cur;
int n = nums.size();
vector<vector<vector<int>>> dp(nums.size()+1,vector<vector<int>>(nums.size()+1,vector<int>(nums.size()+1,-1)));
// vector<vector<int>> ndp(nums.size()+1,vector<int>(nums.size()+1));
gensubsets(cur,nums,0,k,0,ans,dp);
return ans;
}
};
Can you help me to find why it fails certain test cases?
Is it because cur.size() as a state is non-dependable/repeatable?
Here’s my approach overall:
Used cursame to keep track of number of times we have a[i] != a[i+1] and went through all the possibilities using the take nottake approach.
Uniqueone69 is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.