Given a sequence of integers ,find a subsequence of largest length such that in the subsequence adjacent elements are not equal at most k times. n<=1e3,k<=n<=1e3 .. Any Hints or ideas?↵
↵
*upd*: Thank You everyone.↵
Final solution:↵
↵
suppose u are at index i.say p denotes index of prev elements.say given array is a ;↵
dp[x][y]=max length when u have explored only till x index and atmost y non equla adjacent pairs.↵
↵
brute force dp(O(n3)):-↵
for(int p=0;p<i;p++)↵
{ for(int j=0;j<k;j++)↵
{int a=-1,b=-1;↵
if(a[i]==a[p]) a=dp[p][j]+1;↵
else if(j>=1) b=dp[p][j-1]+1;↵
↵
dp[i][j]=max{dp[i][j],a,b}↵
}↵
↵
}↵
↵
Very easy to optimise:↵
we want just max out of dp[0 ....... i-1][j] and max out of dp[0...... i-1][j-1].Hence for all j's we can map the j's as the max attained till now as we proceed from indices.I have tried to be accurate .Still U find some thing to be correct pls inform.↵
↵
*upd*: Thank You everyone.↵
Final solution:↵
↵
suppose u are at index i.say p denotes index of prev elements.say given array is a ;↵
dp[x][y]=max length when u have explored only till x index and atmost y non equla adjacent pairs.↵
↵
brute force dp(O(n3)):-↵
for(int p=0;p<i;p++)↵
{ for(int j=0;j<k;j++)↵
{int a=-1,b=-1;↵
if(a[i]==a[p]) a=dp[p][j]+1;↵
else if(j>=1) b=dp[p][j-1]+1;↵
↵
dp[i][j]=max{dp[i][j],a,b}↵
}↵
↵
}↵
↵
Very easy to optimise:↵
we want just max out of dp[0 ....... i-1][j] and max out of dp[0...... i-1][j-1].
