this can be done in O(n) using DP:
for (i=n-1;i>=0;i--){
dp[i]=max(dp[i+2],dp[i+3]); // usual
if (a[i]==a[i+1]) // excellent size 2
dp[i]=max(dp[i],2+dp[i+2]);
if (a[i]==a[i+1] && a[i+1]==a[i+2]) //excellent size 3
dp[i]=max(dp[i],2+dp[i+3]);
if (a[i]==a[i+1] || a[i]==a[i+2] || a[i+1]==a[i+2]) // good
dp[i]=max(dp[i],1+dp[i+3]);
}
the result is in dp[0]
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
