I did this DP problem, somehow i got WA in TC 15.
I got frustrated, so I saw those comments, I removed memset (manually initialize dp to -1), I tried to use long long, even though i think that changing array data type to long long is unecessary, and I tried every test case that’s possibly wrong, and yes my code giving correct answer, and yes I do read the first properties and second properties from the problem statement.
Here’s my code:
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int dp[N];
int a[N];
int n;
void debug (int a){
cout <<"DEBUG = " << a << endl;
}
int f(int x){
if (x>=n) return 0;
if (x==n-1) return 1;
int &ret = dp[x];
if (ret!=-1) return ret;
for (int i=x; i<n; i++){
if (a[x]>0 && a[i]<0 && a[x] < -a[i]) ret = max(ret,f(i)+1);
else if (a[x]<0 && a[i]>0 && -a[x] < a[i]) ret = max(ret,f(i)+1);
else ret = max(ret,f(i+1));
}
return ret;
}
int main(){
scanf("%d",&n);
for (int i=0; i<n; i++) scanf("%d",&a[i]);
for (int i=0; i<N; i++) dp[i]=-1;
printf("%d\n",f(0));
}
/*
if stuck on test case #15 :
5
-5 -2 4 2 -1
expected output : 2 (Already Correct)
1
2
output: 1 (Already Correct)
*/
That’s it, I hope anyone can help me what’s wrong, or any Test Case.