Length of Longest Balanced Subsequence | PHP program to find length of the longest balanced subsequence ; Considering all balanced substrings of length 2 ; Considering all other substrings ; Driver Code
< ? php function maxLength ( $ s , $ n ) { $ dp = array_fill ( 0 , $ n , array_fill ( 0 , $ n , NULL ) ) ; for ( $ i = 0 ; $ i < $ n - 1 ; $ i ++ ) if ( $ s [ $ i ] == ' ( ' && $ s [ $ i + 1 ] == ' ) ' ) $ dp [ $ i ] [ $ i + 1 ] = 2 ; for ( $ l = 2 ; $ l < $ n ; $ l ++ ) { for ( $ i = 0 , $ j = $ l ; $ j < $ n ; $ i ++ , $ j ++ ) { if ( $ s [ $ i ] == ' ( ' && $ s [ $ j ] == ' ) ' ) $ dp [ $ i ] [ $ j ] = 2 + $ dp [ $ i + 1 ] [ $ j - 1 ] ; for ( $ k = $ i ; $ k < $ j ; $ k ++ ) $ dp [ $ i ] [ $ j ] = max ( $ dp [ $ i ] [ $ j ] , $ dp [ $ i ] [ $ k ] + $ dp [ $ k + 1 ] [ $ j ] ) ; } } return $ dp [ 0 ] [ $ n - 1 ] ; } $ s = " ( ) ( ( ( ( ( ( ) " ; $ n = strlen ( $ s ) ; echo maxLength ( $ s , $ n ) . " STRNEWLINE " ; ? >