Hey Guys!
I was trying to solve the following problem using DP. Here’s my approach →
#include <iostream>
#include <cstring>
const int nax = 2e2+1;
int A[nax];
int dp[nax][nax][4];
int solve(int left, int right, int change, int prev) {
int nchange = A[left]==prev?change:change+1;
if (nchange>=3) return 0;
if (left>right) return 0;
if (left==right) return 1;
if (~dp[left][right][change]) return dp[left][right][change];
int include = 0;
if(A[left]==A[right]) {
nchange = A[left]==prev?change:change+1;
include = 2+solve(left+1,right-1,nchange,A[left]);
}
int excludel = solve(left+1,right,change,prev);
int excluder = solve(left,right-1,change,prev);
int ans = std::max(include, std::max(excludel,excluder));
dp[left][right][change] = ans;
return dp[left][right][change];
}
int main() {
std::ios_base::sync_with_stdio(0);
int T;
std::cin >> T;
while (T--) {
int N;
std::cin >> N;
for (int i=0; i<N; i++) std::cin >> A[i];
memset(dp, -1, sizeof(dp));
std::cout << solve(0, N-1, 0, -1) << "\n";
}
return 0;
}
However, this isn’t the right solution and fails at some test cases which I cannot see. Can someone please point out what the flaw in this solution is? or like where my logic is wrong?