Maximize the subarray sum after multiplying all elements of any subarray with X | Java 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
class GFG { static int N = 5 ; static int func ( int idx , int cur , int a [ ] , int dp [ ] [ ] , 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 = 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 ; } static int getMaximumSum ( int a [ ] , int n , int x ) { int dp [ ] [ ] = new int [ n ] [ 3 ] ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < 3 ; j ++ ) { dp [ i ] [ j ] = - 1 ; } } int maxi = 0 ; for ( int i = 0 ; i < n ; i ++ ) { maxi = Math . max ( maxi , func ( i , 0 , a , dp , n , x ) ) ; } return maxi ; } public static void main ( String [ ] args ) { int a [ ] = { - 3 , 8 , - 2 , 1 , - 6 } ; int n = a . length ; int x = - 1 ; System . out . println ( getMaximumSum ( a , n , x ) ) ; } }