Maximize the subarray sum after multiplying all elements of any subarray with X | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define N  5 NEW_LINE int func ( int idx , int cur , int a [ ] , int dp [ N ] [ 3 ] , int n , int x ) { if ( idx == n ) return 0 ; if ( dp [ idx ] [ cur ] != -1 ) return dp [ idx ] [ cur ] ; int 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 ; } int getMaximumSum ( int a [ ] , int n , int x ) { int dp [ n ] [ 3 ] ; memset ( dp , -1 , sizeof dp ) ; int maxi = 0 ; for ( int i = 0 ; i < n ; i ++ ) maxi = max ( maxi , func ( i , 0 , a , dp , n , x ) ) ; return maxi ; } int main ( ) { int a [ ] = { -3 , 8 , -2 , 1 , -6 } ; int n = sizeof ( a ) / sizeof ( a [ 0 ] ) ; int x = -1 ; cout << getMaximumSum ( a , n , x ) ; return 0 ; }