Maximize the subarray sum after multiplying all elements of any subarray with X | PHP 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 ; 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
< ? php $ N = 5 ; function func ( $ idx , $ cur , $ a , $ dp , $ n , $ x ) { if ( $ idx == $ n ) return 0 ; if ( $ dp [ $ idx ] [ $ cur ] != -1 ) return $ dp [ $ idx ] [ $ cur ] ; $ ans = 0 ; if ( $ cur == 0 ) { $ ans = max ( $ ans , $ a [ $ idx ] + func ( $ idx + 1 , 0 , $ a , $ dp , $ n , $ x ) ) ; $ ans = max ( $ ans , $ x * $ a [ $ idx ] + func ( $ idx + 1 , 1 , $ a , $ dp , $ n , $ x ) ) ; } else if ( $ cur == 1 ) { $ ans = max ( $ ans , $ x * $ a [ $ idx ] + func ( $ idx + 1 , 1 , $ a , $ dp , $ n , $ x ) ) ; $ ans = max ( $ ans , $ a [ $ idx ] + func ( $ idx + 1 , 2 , $ a , $ dp , $ n , $ x ) ) ; } else $ ans = max ( $ ans , $ a [ $ idx ] + func ( $ idx + 1 , 2 , $ a , $ dp , $ n , $ x ) ) ; return $ dp [ $ idx ] [ $ cur ] = $ ans ; } function getMaximumSum ( $ a , $ n , $ x ) { $ dp = array ( array ( ) ) ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) { for ( $ j = 0 ; $ j < 3 ; $ j ++ ) { $ dp [ $ i ] [ $ j ] = -1 ; } } $ maxi = 0 ; for ( $ i = 0 ; $ i < $ n ; $ i ++ ) $ maxi = max ( $ maxi , func ( $ i , 0 , $ a , $ dp , $ n , $ x ) ) ; return $ maxi ; } $ a = array ( -3 , 8 , -2 , 1 , -6 ) ; $ n = count ( $ a ) ; $ x = -1 ; echo getMaximumSum ( $ a , $ n , $ x ) ; ? >