AC in one GO!

nailed it :)

A modified Matrix Chain Multiplication algorithm (MCM) can solve it in O(n^3) using the dynamic programming(dp) approach. The idea is to generate all possible combination of sub-problems and derive a formula that solves the problem in bottom-up manner. Assuming you know the dp solution of MCM, let M[n][n] be a table where M[i,j] stores the solution of elements from i to j in given string. Generate all possible combination of array-index i, j, k i.e. i<=k<j. In the table each range(i to j) can have two properties like:

sweet = number of 1’s in range(i,j)

total = total segments of best choice i.e. sweet>sour.It’s the solution for element(i to j).

dp table can be of type rock like:

struct rock

{

int sweet,total;

};

Now in all possible combination of i, j, k there can be four cases:

1.(i == k) && (k+1 == j)

2. (i == k)

3. (k+1 == j)

4.not any of three above i.e. i, k, k+1, j are distinct.

Main logic: If number of 1’s (sweets) in between element index (i to j) < (total elements in range)/2 , total elements in range is the optimal solution.

otherwise, optimal solution = summation of sub-problems.

Now fitting the logic into the table for all those 4 cases and taking the maximum in each step will yield an optimal solution.

Phew ....Accepted....Missing condition to compare zeros and ones

recursion with memo accepted !! AC in 1st attempt.