Need some help to find recursive and dp solution for SPOJ BORW BlackOrWhite Problem

Hi,
I have been trying to find the recursive solution for SPOJ BORW(Black or White) problem , but none of the recursive logic seems to work.
I understood that the recursive equation will be based on the logic that any ball can be either painted black or white or none , but couldn’t turn it into logical terms .
Problem link link text

Since recurisve solution has been provided now , I was trying to convert this solution to dp solution using 3D dp array of which one of the state whould be array index. For the next two states I am little confused bcoz if I take array values as the other two indexes , then the dp size would be too large . Any suggestion what should be the other two states of dp ??
Any hints will be appreciated. Thanks

I have tried to implement the solution here : Link.
In case of any doubt feel free to ask!

1 Like

@vivek_1998299 , thanks for your response,
i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??
link text

@vivek_1998299 , thanks for your response,
i too didn’t get how this algorithm is working , although i tried to created one solution with your algo , but it is not working . Please have a look and suggest me what changes are required ??
link text

Hi dishant . thanks a lot for your resposne. I guess i got confused in making this recursive solution bcoz i was trying to implement dp along with recursion :stuck_out_tongue: :stuck_out_tongue: ( feeling a lot silly now) . thanks anyway :slight_smile:

Infact I too am trying to figure out a dp solution to this since yesterday (yeah I am pretty bad at dp xD).
Have you figured out one yet? If yes please share it!

U can easily do this using 2d Dp,dp[x][y] denotes the maximum number of painted if the xth ,and yth index are the last in increasing and decreasing subsequences.

dp[x][y]=max(dp[i][y]+1)–>(for i<x and arr[i]<arr[x])

dp[x][y]=max(dp[x][i]+1)—>(for i<y and arr[i]>arr[y])

Can you explain a bit more on this and maybe provide pseudocode. I can’t get how this works!

I tried implementing your logic but it didn’t worked. Can you plz see into the code to figure out where I’m going wrong. Code