Maximum length of segments of 0 ' s ▁ and ▁ 1' s | C ++ implementation of above approach ; Recursive Function to find total length of the array Where 1 is greater than zero ; If reaches till end ; If dp is saved ; Finding for each length ; If the character scanned is 1 ; If one is greater than zero , add total length scanned till now ; Continue with next length ; Return the value for start index ; Driver Code ; Size of string ; Calling the function to find the value of function
#include <bits/stdc++.h> NEW_LINE using namespace std ; int find ( int start , string adj , int n , int dp [ ] ) { if ( start == n ) return 0 ; if ( dp [ start ] != -1 ) return dp [ start ] ; dp [ start ] = 0 ; int one = 0 , zero = 0 , k ; for ( k = start ; k < n ; k ++ ) { if ( adj [ k ] == '1' ) one ++ ; else zero ++ ; if ( one > zero ) dp [ start ] = max ( dp [ start ] , find ( k + 1 , adj , n , dp ) + k - start + 1 ) ; else dp [ start ] = max ( dp [ start ] , find ( k + 1 , adj , n , dp ) ) ; } return dp [ start ] ; } int main ( ) { string adj = "100110001010001" ; int n = adj . size ( ) ; int dp [ n + 1 ] ; memset ( dp , -1 , sizeof ( dp ) ) ; cout << find ( 0 , adj , n , dp ) << endl ; return 0 ; }