sbgobbur
BAN USER1) divide the given string into two halves
2) find continuous zeros count in left half using recursion
3) find continuous zeros count in right half using recursion
4) find continuous zeros count in left part that touches the mid point
5) find continuous zeros count in right part that touches the mid point
6) add counts found in (4) & (5)
7) return max of (2), (3) & (6)
int get_max_zeros(char* binstr, int lo, int hi) {
if (lo > hi)
return 0;
if (lo == hi)
return (binstr[lo] == '0')? 1 : 0;
int mid = lo + (hi-lo)/2;
int left_crossing_count = 0;
for (int i=mid; i>=lo; i--)
if (binstr[i] != '0')
break;
else
left_crossing_count++;
int right_crossing_count = 0;
for (int i=mid+1; i<=hi; i++)
if (binstr[i] != '0')
break;
else
right_crossing_count++;
int crossing_count = left_crossing_count + right_crossing_count;
int left_count = get_max_zeros(binstr, lo, mid);
int right_count = get_max_zeros(binstr, mid+1, hi);
int max1 = crossing_count > left_count? crossing_count : left_count;
int max2 = max1 > right_count? max1 : right_count;
return max2;
}
- sbgobbur July 21, 2015