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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.