Maximize the subarray sum after multiplying all elements of any subarray with X | JavaScript implementation of the approach ; Function to return the maximum sum ; Base case ; If already calculated ; If no elements have been chosen ; Do not choose any element and use Kadane 's algorithm by taking max ; Choose the sub - array and multiply x ; Choose the sub - array and multiply x ; End the sub - array multiplication ; } else No more multiplication ; Memoize and return the answer ; Function to get the maximum sum ; Initialize dp with - 1 ; Iterate from every position and find the maximum sum which is possible ; Driver code
var N = 5 ; function func ( idx , cur , a , dp , n , x ) { if ( idx == n ) { return 0 ; } if ( dp [ idx ] [ cur ] != - 1 ) { return dp [ idx ] [ cur ] ; } var ans = 0 ; if ( cur == 0 ) { ans = Math . max ( ans , a [ idx ] + func ( idx + 1 , 0 , a , dp , n , x ) ) ; ans = Math . max ( ans , x * a [ idx ] + func ( idx + 1 , 1 , a , dp , n , x ) ) ; } else if ( cur == 1 ) { ans = Math . max ( ans , x * a [ idx ] + func ( idx + 1 , 1 , a , dp , n , x ) ) ; ans = Math . max ( ans , a [ idx ] + func ( idx + 1 , 2 , a , dp , n , x ) ) ; { ans = Math . max ( ans , a [ idx ] + func ( idx + 1 , 2 , a , dp , n , x ) ) ; } return dp [ idx ] [ cur ] = ans ; } function getMaximumSum ( a , n , x ) { var dp = Array ( n ) . fill ( ) . map ( ( ) => Array ( 3 ) . fill ( 0 ) ) ; for ( i = 0 ; i < n ; i ++ ) { for ( j = 0 ; j < 3 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } var maxi = 0 ; for ( i = 0 ; i < n ; i ++ ) { maxi = Math . max ( maxi , func ( i , 0 , a , dp , n , x ) ) ; } return maxi ; } var a = [ - 3 , 8 , - 2 , 1 , - 6 ] ; var n = a . length ; var x = - 1 ; document . write ( getMaximumSum ( a , n , x ) ) ;