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 sumint 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 sumint 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 codeint 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 approachclass GFG{ static int N = 5;// Function to return the maximum sumstatic 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 sumstatic 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 codepublic 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 approachN = 5# Function to return the maximum sumdef 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 sumdef 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 codea = [ -3, 8, -2, 1, -6 ] n = len(a) x = -1print(getMaximumSum(a, n, x)) # This code is contributed by ihritik |
C#
// C# implementation of the approachusing System;class GFG{ static int N = 5;// Function to return the maximum sumstatic 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 sumstatic 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 codepublic 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
15
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 sumint 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 codeint 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 sumdef 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 codeif __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 sumfunction 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 codelet a = [-3, 8, -2, 1, -6];let n = a.length;let x = -1;// function callconsole.log(getMaximumSum(a, n, x)); |
Output:
15
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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!