I was trying to solve This problem of Google APC 2015.

I did a o(n^4) Dp for finding the maximum number of elements that can be removed, keeping the starting and ending index of the array(say i,j) and two loops for transition in a state for finding all possible triplets in i to j range.

Let (a,b,c) is a triplet possible such that b-a=c-b=k where i<=a<=b<=c<=j

dp[i][j]=max(dp[i][j],3+dp[i][a-1]+dp[a+1][b-1]+dp[b+1][c-1]+dp[c+1][j])

Can someone give a better complexity solution...

Thanks