Maximize the subarray sum after multiplying all elements of any subarray with X

0 0 13 minutes read

Given an array arr[] of N integers and an integer X. We can choose any sub-array and multiply all its element by X. After multiplication, find the sub-array with the maximum sum. The task is to multiply the sub-array in such a way that the final sub-array sum is maximized.
Examples:

Input: arr[] = { -3, 8, -2, 1, -6 }, X = -1
Output: 15
Choose the sub-array with {-2, 1, -6} and multiply X.
Now the new array is {-3, 8, 2, -1, 6} whose maximum sub-array sum is 15.
Input: arr[] = {1, 2, 4, -10}, X = 2
Output: 14

Approach: The problem cannot be solved using a greedy approach. Greedy approach fails in many cases one of them being a[] = { -3, 8, -2, 1, 6 } and x = -1. We will use Dynamic Programming to solve the above problem. Let dp[ind][state], where ind is the current index in the array and there are 3 states.

The first state defines that no sub-array has been chosen till index ind to be multiplied with X.
The second state defines that the current element at index ind is in the sub-array which is multiplied with X.
The third state defines that the sub-array has already been chosen.

Kadane’s algorithm has been used along with DP to get the maximum subarray sum simultaneously.
Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define N 5
 
// Function to return the maximum sum
int func(int idx, int cur, int a[], int dp[N][3], int n, int x)
{
 
    // Base case
    if (idx == n)
        return 0;
 
    // If already calculated
    if (dp[idx][cur] != -1)
        return dp[idx][cur];
 
    int ans = 0;
 
    // If no elements have been chosen
    if (cur == 0) {
 
        // Do not choose any element and use
        // Kadane's algorithm by taking max
        ans = max(ans, a[idx] + func(idx + 1, 0, a, dp, n, x));
 
        // Choose the sub-array and multiply x
        ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x));
    }
    else if (cur == 1) {
 
        // Choose the sub-array and multiply x
        ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x));
 
        // End the sub-array multiplication
        ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x));
    }
    else
 
        // No more multiplication
        ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x));
 
    // Memoize and return the answer
    return dp[idx][cur] = ans;
}
 
// Function to get the maximum sum
int getMaximumSum(int a[], int n, int x)
{
 
    // Initialize dp with -1
    int dp[n][3];
    memset(dp, -1, sizeof dp);
 
    // Iterate from every position and find the
    // maximum sum which is possible
    int maxi = 0;
    for (int i = 0; i < n; i++)
        maxi = max(maxi, func(i, 0, a, dp, n, x));
 
    return maxi;
}
 
// Driver code
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;
}

Java

// Java implementation of the approach
class GFG
{
 
    static int N = 5;
 
// Function to return the maximum sum
static int func(int idx, int cur, int a[],
                int dp[][], int n, int x)
{
 
    // Base case
    if (idx == n)
    {
        return 0;
    }
 
    // If already calculated
    if (dp[idx][cur] != -1)
    {
        return dp[idx][cur];
    }
 
    int ans = 0;
 
    // If no elements have been chosen
    if (cur == 0)
    {
 
        // Do not choose any element and use
        // Kadane's algorithm by taking max
        ans = Math.max(ans, a[idx] + 
                func(idx + 1, 0, a, dp, n, x));
 
        // Choose the sub-array and multiply x
        ans = Math.max(ans, x * a[idx] + 
                func(idx + 1, 1, a, dp, n, x));
    } 
    else if (cur == 1)
    {
 
        // Choose the sub-array and multiply x
        ans = Math.max(ans, x * a[idx] + 
                func(idx + 1, 1, a, dp, n, x));
 
        // End the sub-array multiplication
        ans = Math.max(ans, a[idx] + 
                func(idx + 1, 2, a, dp, n, x));
    } 
    else // No more multiplication
    {
        ans = Math.max(ans, a[idx] + 
                func(idx + 1, 2, a, dp, n, x));
    }
 
    // Memoize and return the answer
    return dp[idx][cur] = ans;
}
 
// Function to get the maximum sum
static int getMaximumSum(int a[], int n, int x)
{
 
    // Initialize dp with -1
    int dp[][] = new int[n][3];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            dp[i][j] = -1;
        }
    }
 
    // Iterate from every position and find the
    // maximum sum which is possible
    int maxi = 0;
    for (int i = 0; i < n; i++)
    {
        maxi = Math.max(maxi, func(i, 0, a, dp, n, x));
    }
 
    return maxi;
}
 
// Driver code
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));
 
}
}
 
// This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach
 
N = 5
 
# Function to return the maximum sum
def func(idx, cur, a, dp, n, x) :
  
 
    # Base case
    if (idx == n) :
        return 0
 
    # If already calculated
    if (dp[idx][cur] != -1):
        return dp[idx][cur] 
 
    ans = 0
 
    # If no elements have been chosen
    if (cur == 0) :
 
        # Do not choose any element and use
        # Kadane's algorithm by taking max
        ans = max(ans, a[idx] + func(idx + 1, 0, a, dp, n, x)) 
 
        # Choose the sub-array and multiply x
        ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x)) 
      
    elif (cur == 1) :
 
        # Choose the sub-array and multiply x
        ans = max(ans, x * a[idx] + func(idx + 1, 1, a, dp, n, x)) 
 
        # End the sub-array multiplication
        ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x)) 
      
    else :
 
        # No more multiplication
        ans = max(ans, a[idx] + func(idx + 1, 2, a, dp, n, x)) 
 
    # Memoize and return the answer
    dp[idx][cur] = ans 
     
    return dp[idx][cur]
  
 
# Function to get the maximum sum
def getMaximumSum(a, n, x) :
  
 
    # Initialize dp with -1
    dp = [[-1 for i in range(3)] for j in range(n)]
     
 
    # Iterate from every position and find the
    # maximum sum which is possible
    maxi = 0
    for i in range (0, n) :
        maxi = max(maxi, func(i, 0, a, dp, n, x)) 
 
    return maxi 
  
 
# Driver code
 
a =  [ -3, 8, -2, 1, -6 ]   
n = len(a) 
x = -1
 
print(getMaximumSum(a, n, x)) 
 
# This code is contributed by ihritik

C#

// C# implementation of the approach
using System;
 
class GFG
{
 
    static int N = 5;
 
// Function to return the maximum sum
static int func(int idx, int cur, int []a,
                int [,]dp, int n, int x)
{
 
    // Base case
    if (idx == n)
    {
        return 0;
    }
 
    // If already calculated
    if (dp[idx,cur] != -1)
    {
        return dp[idx,cur];
    }
 
    int ans = 0;
 
    // If no elements have been chosen
    if (cur == 0)
    {
 
        // Do not choose any element and use
        // Kadane's algorithm by taking max
        ans = Math.Max(ans, a[idx] + 
                func(idx + 1, 0, a, dp, n, x));
 
        // Choose the sub-array and multiply x
        ans = Math.Max(ans, x * a[idx] + 
                func(idx + 1, 1, a, dp, n, x));
    } 
    else if (cur == 1)
    {
 
        // Choose the sub-array and multiply x
        ans = Math.Max(ans, x * a[idx] + 
                func(idx + 1, 1, a, dp, n, x));
 
        // End the sub-array multiplication
        ans = Math.Max(ans, a[idx] + 
                func(idx + 1, 2, a, dp, n, x));
    } 
    else // No more multiplication
    {
        ans = Math.Max(ans, a[idx] + 
                func(idx + 1, 2, a, dp, n, x));
    }
 
    // Memoize and return the answer
    return dp[idx,cur] = ans;
}
 
// Function to get the maximum sum
static int getMaximumSum(int []a, int n, int x)
{
 
    // Initialize dp with -1
    int [,]dp = new int[n,3];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            dp[i,j] = -1;
        }
    }
 
    // Iterate from every position and find the
    // maximum sum which is possible
    int maxi = 0;
    for (int i = 0; i < n; i++)
    {
        maxi = Math.Max(maxi, func(i, 0, a, dp, n, x));
    }
 
    return maxi;
}
 
// Driver code
public static void Main(String[] args) 
{
    int []a = {-3, 8, -2, 1, -6};
    int n = a.Length;
    int x = -1;
    Console.WriteLine(getMaximumSum(a, n, x));
 
}
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

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

PHP

<?php
// PHP implementation of the approach 
 
$N = 5; 
 
// Function to return the maximum sum 
function func($idx, $cur, $a, $dp, $n, $x) 
{ 
 
    // Base case 
    if ($idx == $n) 
        return 0; 
 
    // If already calculated 
    if ($dp[$idx][$cur] != -1) 
        return $dp[$idx][$cur]; 
 
    $ans = 0; 
 
    // If no elements have been chosen 
    if ($cur == 0) 
    { 
 
        // Do not choose any element and use 
        // Kadane's algorithm by taking max 
        $ans = max($ans, $a[$idx] + 
                func($idx + 1, 0, $a, $dp, $n, $x)); 
 
        // Choose the sub-array and multiply x 
        $ans = max($ans, $x * $a[$idx] + 
                func($idx + 1, 1, $a, $dp, $n, $x)); 
    } 
    else if ($cur == 1)
    { 
 
        // Choose the sub-array and multiply x 
        $ans = max($ans, $x * $a[$idx] + 
                func($idx + 1, 1, $a, $dp, $n, $x)); 
 
        // End the sub-array multiplication 
        $ans = max($ans, $a[$idx] + 
                func($idx + 1, 2, $a, $dp, $n, $x)); 
    } 
    else
 
        // No more multiplication 
        $ans = max($ans, $a[$idx] + 
                func($idx + 1, 2, $a, $dp,$n, $x)); 
 
    // Memoize and return the answer 
    return $dp[$idx][$cur] = $ans; 
} 
 
// Function to get the maximum sum 
function getMaximumSum($a, $n, $x) 
{ 
 
    // Initialize dp with -1 
    $dp = array(array()) ;
     
    for($i = 0; $i < $n; $i++)
    {
        for($j = 0; $j < 3; $j++)
        {
            $dp[$i][$j] = -1;
        }
    }
 
    // Iterate from every position and find the 
    // maximum sum which is possible 
    $maxi = 0; 
    for ($i = 0; $i < $n; $i++) 
        $maxi = max($maxi, func($i, 0, $a, $dp, $n, $x)); 
 
    return $maxi; 
} 
 
    // Driver code 
    $a = array( -3, 8, -2, 1, -6 ); 
    $n = count($a) ;
    $x = -1; 
 
    echo getMaximumSum($a, $n, $x); 
     
    // This code is contributed by Ryuga
?>

Output

Time Complexity: O(N * 3)
Auxiliary Space: O(N * 3)

Efficient approach : Using DP Tabulation method ( Iterative approach )

The approach to solve this problem is same but DP tabulation(bottom-up) method is better then Dp + memoization(top-down) because memoization method needs extra stack space of recursion calls.

Steps to solve this problem :

Create a DP to store the solution of the subproblems.
Initialize the DP with base cases
Now Iterate over subproblems to get the value of current problem form previous computation of subproblems stored in DP.
Create a variable ans to keep track of values of DP in each condition.
After iteration from loop create a variable maxi to store the maximum sum and update it by iterate over Dp.
Return the final solution stored in maxi.

Implementation :

C++

#include <bits/stdc++.h>
using namespace std;
#define N 5
 
// Function to return the maximum sum
int getMaximumSum(int a[], int n, int x)
{
    int dp[n][3];
 
    // Initializing the dp array
    for(int i=0; i<n; i++){
        dp[i][0] = a[i];
        dp[i][1] = a[i]*x;
        dp[i][2] = a[i];
    }
 
    // Applying the recurrence relation
    for(int i=n-2; i>=0; i--){
        for(int j=0; j<3; j++){
           
              // to track the answer in each condition
            int ans = 0;
            if(j==0){
                ans = max(dp[i][j], dp[i+1][j]+a[i]);
                ans = max(ans, dp[i+1][j+1]+x*a[i]);
            }
            else if(j==1){
                ans = max(dp[i][j], dp[i+1][j]+x*a[i]);
                ans = max(ans, dp[i+1][j+1]+a[i]);
            }
            else{
                ans = max(dp[i][j], dp[i+1][j]+a[i]);
            }
           
              // update DP 
            dp[i][j] = ans;
        }
    }
 
    // Finding the maximum sum from dp array
    int maxi = 0;
    for (int i = 0; i < n; i++)
        maxi = max(maxi, dp[i][0]);
     
      // return final answer
    return maxi;
}
 
// Driver code
int main()
{
    int a[] = { -3, 8, -2, 1, -6 };
    int n = sizeof(a) / sizeof(a[0]);
    int x = -1;
    // function call
    cout << getMaximumSum(a, n, x);
 
    return 0;
}

Java

import java.util.*;
 
public class Main {
 
  public static int getMaximumSum(int[] a, int n, int x)
  {
 
    // Initializing the dp array
    int[][] dp = new int[n][3];
    for (int i = 0; i < n; i++) {
      dp[i][0] = a[i];
      dp[i][1] = a[i] * x;
      dp[i][2] = a[i];
    }
 
    // Applying the recurrence relation
    for (int i = n - 2; i >= 0; i--) {
      for (int j = 0; j < 3; j++) {
 
        // to track the answer in each condition
        int ans = 0;
        if (j == 0) {
          ans = Math.max(dp[i][j],
                         dp[i + 1][j] + a[i]);
          ans = Math.max(ans, dp[i + 1][j + 1]
                         + x * a[i]);
        }
        else if (j == 1) {
          ans = Math.max(dp[i][j],
                         dp[i + 1][j] + x * a[i]);
          ans = Math.max(ans,
                         dp[i + 1][j + 1] + a[i]);
        }
        else {
          ans = Math.max(dp[i][j],
                         dp[i + 1][j] + a[i]);
        }
 
        // update DP
        dp[i][j] = ans;
      }
    }
 
    // Finding the maximum sum from dp array
    int maxi = 0;
    for (int i = 0; i < n; i++) {
      maxi = Math.max(maxi, dp[i][0]);
    }
 
    // return final answer
    return maxi;
  }
 
  public static void main(String[] args)
  {
    int[] a = { -3, 8, -2, 1, -6 };
    int n = a.length;
    int x = -1;
 
    // function call
    System.out.println(getMaximumSum(a, n, x));
  }
}
 
// This code is contributed by user_dtewbxkn77n

Python3

# Function to return the maximum sum
def getMaximumSum(a, n, x):
   
    # Initializing the dp array
    dp = [[0 for j in range(3)] for i in range(n)]
    for i in range(n):
        dp[i][0] = a[i]
        dp[i][1] = a[i] * x
        dp[i][2] = a[i]
 
    # Applying the recurrence relation
    for i in range(n-2, -1, -1):
        for j in range(3):
           
            # to track the answer in each condition
            ans = 0
            if j == 0:
                ans = max(dp[i][j], dp[i+1][j]+a[i])
                ans = max(ans, dp[i+1][j+1]+x*a[i])
            elif j == 1:
                ans = max(dp[i][j], dp[i+1][j]+x*a[i])
                ans = max(ans, dp[i+1][j+1]+a[i])
            else:
                ans = max(dp[i][j], dp[i+1][j]+a[i])
             
            # update DP
            dp[i][j] = ans
 
    # Finding the maximum sum from dp array
    maxi = 0
    for i in range(n):
        maxi = max(maxi, dp[i][0])
 
    # return final answer
    return maxi
 
# Driver code
if __name__ == '__main__':
    a = [-3, 8, -2, 1, -6]
    n = len(a)
    x = -1
     
    # function call
    print(getMaximumSum(a, n, x))

C#

using System;
 
class Program {
    const int N = 5;
 
    // Function to return the maximum sum
    static int GetMaximumSum(int[] a, int n, int x)
    {
        int[, ] dp = new int[n, 3];
 
        // Initializing the dp array
        for (int i = 0; i < n; i++) {
            dp[i, 0] = a[i];
            dp[i, 1] = a[i] * x;
            dp[i, 2] = a[i];
        }
 
        // Applying the recurrence relation
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j < 3; j++) {
                // to track the answer in each condition
                int ans = 0;
                if (j == 0) {
                    ans = Math.Max(dp[i, j],
                                   dp[i + 1, j] + a[i]);
                    ans = Math.Max(ans, dp[i + 1, j + 1]
                                            + x * a[i]);
                }
                else if (j == 1) {
                    ans = Math.Max(dp[i, j],
                                   dp[i + 1, j] + x * a[i]);
                    ans = Math.Max(ans,
                                   dp[i + 1, j + 1] + a[i]);
                }
                else {
                    ans = Math.Max(dp[i, j],
                                   dp[i + 1, j] + a[i]);
                }
 
                // update DP
                dp[i, j] = ans;
            }
        }
 
        // Finding the maximum sum from dp array
        int maxi = 0;
        for (int i = 0; i < n; i++) {
            maxi = Math.Max(maxi, dp[i, 0]);
        }
 
        // return final answer
        return maxi;
    }
 
    // Driver code
    static void Main()
    {
        int[] a = { -3, 8, -2, 1, -6 };
        int n = a.Length;
        int x = -1;
        // function call
        Console.WriteLine(GetMaximumSum(a, n, x));
    }
}

Javascript

// Function to return the maximum sum
function getMaximumSum(a, n, x) {
    // Initializing the dp array
    let dp = Array.from({ length: n }, () => Array(3).fill(0));
    for (let i = 0; i < n; i++) {
        dp[i][0] = a[i];
        dp[i][1] = a[i] * x;
        dp[i][2] = a[i];
    }
 
    // Applying the recurrence relation
    for (let i = n - 2; i >= 0; i--) {
        for (let j = 0; j < 3; j++) {
            // to track the answer in each condition
            let ans = 0;
            if (j === 0) {
                ans = Math.max(dp[i][j], dp[i + 1][j] + a[i]);
                ans = Math.max(ans, dp[i + 1][j + 1] + x * a[i]);
            } else if (j === 1) {
                ans = Math.max(dp[i][j], dp[i + 1][j] + x * a[i]);
                ans = Math.max(ans, dp[i + 1][j + 1] + a[i]);
            } else {
                ans = Math.max(dp[i][j], dp[i + 1][j] + a[i]);
            }
            // update DP
            dp[i][j] = ans;
        }
    }
 
    // Finding the maximum sum from dp array
    let maxi = 0;
    for (let i = 0; i < n; i++) {
        maxi = Math.max(maxi, dp[i][0]);
    }
 
    // return final answer
    return maxi;
}
 
// Driver code
let a = [-3, 8, -2, 1, -6];
let n = a.length;
let x = -1;
 
// function call
console.log(getMaximumSum(a, n, x));

Output:

Time Complexity: O(N * 3)
Auxiliary Space: O(N * 3)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!