Burst Balloon to maximize coins | Javascript program burst balloon problem ; Add Bordering Balloons ; Declare DP Array ; For a sub - array from indices left , right This innermost loop finds the last balloon burst ; Driver code ; Size of the array ; Calling function
function getMax ( A , N ) { var B = new Array ( N + 2 ) ; B [ 0 ] = 1 ; B [ N + 1 ] = 1 ; for ( var i = 1 ; i <= N ; i ++ ) B [ i ] = A [ i - 1 ] ; var dp = new Array ( N + 2 ) ; for ( var i = 0 ; i < dp . length ; i ++ ) { dp [ i ] = new Array ( N + 2 ) . fill ( 0 ) ; } for ( var length = 1 ; length < N + 1 ; length ++ ) { for ( var left = 1 ; left < N - length + 2 ; left ++ ) { var right = left + length - 1 ; for ( var last = left ; last < right + 1 ; last ++ ) { dp [ left ] [ right ] = Math . max ( dp [ left ] [ right ] , dp [ left ] [ last - 1 ] + B [ left - 1 ] * B [ last ] * B [ right + 1 ] + dp [ last + 1 ] [ right ] ) ; } } } return dp [ 1 ] [ N ] ; } var A = [ 1 , 2 , 3 , 4 , 5 ] ; var N = A . length ; document . write ( getMax ( A , N ) ) ;