Maximize the subarray sum after multiplying all elements of any subarray with X | Python3 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
N = 5 NEW_LINE def func ( idx , cur , a , dp , n , x ) : NEW_LINE INDENT if ( idx == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ idx ] [ cur ] != - 1 ) : NEW_LINE INDENT return dp [ idx ] [ cur ] NEW_LINE DEDENT ans = 0 NEW_LINE if ( cur == 0 ) : NEW_LINE INDENT ans = max ( ans , a [ idx ] + func ( idx + 1 , 0 , a , dp , n , x ) ) NEW_LINE ans = max ( ans , x * a [ idx ] + func ( idx + 1 , 1 , a , dp , n , x ) ) NEW_LINE DEDENT elif ( cur == 1 ) : NEW_LINE INDENT ans = max ( ans , x * a [ idx ] + func ( idx + 1 , 1 , a , dp , n , x ) ) NEW_LINE ans = max ( ans , a [ idx ] + func ( idx + 1 , 2 , a , dp , n , x ) ) NEW_LINE DEDENT else : NEW_LINE INDENT ans = max ( ans , a [ idx ] + func ( idx + 1 , 2 , a , dp , n , x ) ) NEW_LINE DEDENT dp [ idx ] [ cur ] = ans NEW_LINE return dp [ idx ] [ cur ] NEW_LINE DEDENT def getMaximumSum ( a , n , x ) : NEW_LINE INDENT dp = [ [ - 1 for i in range ( 3 ) ] for j in range ( n ) ] NEW_LINE maxi = 0 NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT maxi = max ( maxi , func ( i , 0 , a , dp , n , x ) ) NEW_LINE DEDENT return maxi NEW_LINE DEDENT a = [ - 3 , 8 , - 2 , 1 , - 6 ] NEW_LINE n = len ( a ) NEW_LINE x = - 1 NEW_LINE print ( getMaximumSum ( a , n , x ) ) NEW_LINE