Considering all other substrings
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 ] ; }