ROCK  Sweet and Sour Rock
A manufacturer of sweets has started production of a new type of sweet called rock. Rock comes in sticks composed of onecentimetrelong segments, some of which are sweet, and the rest are sour. Before sale, the rock is broken up into smaller pieces by splitting it at the connections of some segments.
Today's children are very particular about what they eat, and they will only buy a piece of rock if it contains more sweet segments than sour ones. Try to determine the total length of rock which can be sold after breaking up the rock in the best possible way.
Input
The input begins with the integer t, the number of test cases. Then t test cases follow.
For each test case, the first line of input contains one integer N  the length of the stick in centimetres (1<=N<=200). The next line is a sequence of N characters '0' or '1', describing the segments of the stick from the left end to the right end ('0' denotes a sour segment, '1'  a sweet one).
Output
For each test case output a line with a single integer: the total length of rock that can be sold after breaking up the rock in the best possible way.
Example
Sample input: 2 15 100110001010001 16 0010111101100000 Sample output: 9 13
hide comments
nonushikhar:
20160706 02:42:28
easy :) loved it .... hint : matrix chain multiplication 

sarvesh_19:
20160628 22:23:48
recursion with memo accepted !! AC in 1st attempt. 

poojan :
20160611 06:25:01
Getting WA I think i have checked all corner case! PS plz check solution!


prateek1985:
20160414 23:41:15
Great problem to build confidence in dp ! LOVED IT :) ! 

dev:
20160322 14:47:08
Too easy ! 3 wa due to silly mistake :D 

Mohit Rathore:
20160121 07:21:16
Loved solving this :) 

bruceoutdoors:
20151114 11:52:53
@saurabh the answer of 1st test case is 9, because you can break 100110001010001 into 3 segments where there are more 1's than 0's: 10011, 101, and 1. The total length of this 3 segments combined is 9, ergo the answer. Last edit: 20151114 11:58:09 

saurabh:
20151024 20:39:10
how come the answer of 1st test case be 9.


fool_01:
20150919 18:24:58
creating dynamic arrays for every test case giving TLE ?? Last edit: 20150919 18:26:11 

xxbloodysantaxx:
20150711 07:49:23
Problem statement is so unclear!

Added by:  adrian 
Date:  20040803 
Time limit:  7s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 
Resource:  based on a problem from the VII Polish Collegiate Team Programming Contest (AMPPZ), 2002 