Given an array arr[] consisting of N positive integers, the task is to find the maximum product of the subarray sum with the maximum element of that subarray.
Examples:
Input: arr[] = {2, -3, 8, -2, 5}
Output: 88
Explanation:
The required maximum product can be obtained using subarray {8, -2, 5}
Therefore, maximum product = (8 + (-2) + 5) * (8) = 88.Input: arr[] = {-4, 1, -5, 3, 5}
Output: 40
Naive Approach: The simplest approach to solve the problem is to generate all subarrays of the given array and for each subarray, calculate the sum of the subarray, and multiply it with the maximum element in the subarray. Update the maximum product by comparing it with the product calculated. After checking for all the subarrays, print the maximum product obtained after processing all the subarray.
Time Complexity: O(N2)
Auxiliary Space: O(1)
Efficient Approach: The above approach can also be optimized by modifying Kadane’s Algorithm to get the resultant maximum value. Follow the steps below to solve the problem:
- Perform Kadane’s Algorithm according to the following steps:
- Initialize three variables say, largestSum, currSum, currMax as 0.
- Traverse the given array arr[] and perform the following steps;
- Update currSum as currSum + arr[i] and the currMax as max(currMax, arr[i]).
- Update the value of largestSum as max(largestSum, currMax * currSum).
- If the value of currSum is less than 0, then update the value of currMax and currSum as 0.
- After completing the above steps, return the value of largestSum as the resultant maximum product of the sum of the subarray with its maximum element.
- Initialize a variable, say maximumSum as 0 that stores the maximum product of the sum of the subarray with its maximum element.
- Perform the updated Kadane’s Algorithm with the given array and store the returned value in maximumSum.
- Now, update each array element by multiplying each element by (-1) and again perform the updated Kadane’s Algorithm with the updated array so that if the maximum element of any subarray is negative then that combination must be taken into account.
- Update the value of maximumSum to the maximum of maximumSum and the value returned by the above step.
- After completing the above steps, print the value of maximumSum as the result.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to find the maximum product// of the sum of the subarray with its// maximum elementint Kadane(int arr[], int n){ int largestSum = 0, currMax = 0; int currSum = 0; // Traverse the array arr[] for (int i = 0; i < n; i++) { // Increment currSum by a[i] currSum += arr[i]; // Maximize the value of currMax currMax = max(currMax, arr[i]); // Maximize the value of // largestSum largestSum = max(largestSum, currMax * currSum); // If currSum goes less than 0 // then update currSum = 0 if (currSum < 0) { currMax = 0; currSum = 0; } } // Return the resultant value return largestSum;}// Function to maximize the product of// the sum of the subarray with its// maximum elementint maximumWeight(int arr[], int n){ // Find the largest sum of the // subarray int largestSum = Kadane(arr, n); // Multiply each array element // with -1 for (int i = 0; i < n; i++) { arr[i] = -arr[i]; } // Find the largest sum of the // subarray with negation of all // array element largestSum = max(largestSum, Kadane(arr, n)); // Return the resultant maximum // value return largestSum;}// Driver Codeint main(){ int arr[] = { 2, -3, 8, -2, 5 }; int N = sizeof(arr) / sizeof(arr[0]); cout << maximumWeight(arr, N); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Function to find the maximum product // of the sum of the subarray with its // maximum element static int Kadane(int arr[], int n) { int largestSum = 0, currMax = 0; int currSum = 0; // Traverse the array arr[] for (int i = 0; i < n; i++) { // Increment currSum by a[i] currSum += arr[i]; // Maximize the value of currMax currMax = Math.max(currMax, arr[i]); // Maximize the value of // largestSum largestSum = Math.max(largestSum, currMax * currSum); // If currSum goes less than 0 // then update currSum = 0 if (currSum < 0) { currMax = 0; currSum = 0; } } // Return the resultant value return largestSum; } // Function to maximize the product of // the sum of the subarray with its // maximum element static int maximumWeight(int arr[], int n) { // Find the largest sum of the // subarray int largestSum = Kadane(arr, n); // Multiply each array element // with -1 for (int i = 0; i < n; i++) { arr[i] = -arr[i]; } // Find the largest sum of the // subarray with negation of all // array element largestSum = Math.max(largestSum, Kadane(arr, n)); // Return the resultant maximum // value return largestSum; } // Driver Code public static void main(String[] args) { int arr[] = { 2, -3, 8, -2, 5 }; int N = arr.length; System.out.println(maximumWeight(arr, N)); // This code is contributed by Potta Lokesh }} |
Python3
# Python3 program for the above approach# Function to find the maximum product# of the sum of the subarray with its# maximum elementdef Kadane(arr, n): largestSum = 0 currMax = 0 currSum = 0 # Traverse the array arr[] for i in range(n): # Increment currSum by a[i] currSum += arr[i] # Maximize the value of currMax currMax = max(currMax, arr[i]) # Maximize the value of # largestSum largestSum = max(largestSum, currMax * currSum) # If currSum goes less than 0 # then update currSum = 0 if (currSum < 0): currMax = 0 currSum = 0 # Return the resultant value return largestSum# Function to maximize the product of# the sum of the subarray with its# maximum elementdef maximumWeight(arr, n): # Find the largest sum of the # subarray largestSum = Kadane(arr, n) # Multiply each array element # with -1 for i in range(n): arr[i] = -arr[i] # Find the largest sum of the # subarray with negation of all # array element largestSum = max(largestSum, Kadane(arr, n)) # Return the resultant maximum # value return largestSum# Driver Codeif __name__ == '__main__': arr = [ 2, -3, 8, -2, 5 ] N = len(arr) print(maximumWeight(arr, N))# This code is contributed by mohit kumar 29 |
C#
// C# program for the above approachusing System;using System.Collections.Generic;class GFG{// Function to find the maximum product// of the sum of the subarray with its// maximum elementstatic int Kadane(int []arr, int n){ int largestSum = 0, currMax = 0; int currSum = 0; // Traverse the array arr[] for(int i = 0; i < n; i++) { // Increment currSum by a[i] currSum += arr[i]; // Maximize the value of currMax currMax = Math.Max(currMax, arr[i]); // Maximize the value of // largestSum largestSum = Math.Max(largestSum, currMax * currSum); // If currSum goes less than 0 // then update currSum = 0 if (currSum < 0) { currMax = 0; currSum = 0; } } // Return the resultant value return largestSum;}// Function to maximize the product of// the sum of the subarray with its// maximum elementstatic int maximumWeight(int []arr, int n){ // Find the largest sum of the // subarray int largestSum = Kadane(arr, n); // Multiply each array element // with -1 for(int i = 0; i < n; i++) { arr[i] = -arr[i]; } // Find the largest sum of the // subarray with negation of all // array element largestSum = Math.Max(largestSum, Kadane(arr, n)); // Return the resultant maximum // value return largestSum;}// Driver Codepublic static void Main(){ int []arr = { 2, -3, 8, -2, 5 }; int N = arr.Length; Console.Write(maximumWeight(arr, N));}} // This code is contributed by ipg2016107 |
Javascript
<script> // JavaScript Program for the above approach // Function to find the maximum product // of the sum of the subarray with its // maximum element function Kadane(arr, n) { let largestSum = 0, currMax = 0; let currSum = 0; // Traverse the array arr[] for (let i = 0; i < n; i++) { // Increment currSum by a[i] currSum += arr[i]; // Maximize the value of currMax currMax = Math.max(currMax, arr[i]); // Maximize the value of // largestSum largestSum = Math.max(largestSum, currMax * currSum); // If currSum goes less than 0 // then update currSum = 0 if (currSum < 0) { currMax = 0; currSum = 0; } } // Return the resultant value return largestSum; } // Function to maximize the product of // the sum of the subarray with its // maximum element function maximumWeight(arr, n) { // Find the largest sum of the // subarray let largestSum = Kadane(arr, n); // Multiply each array element // with -1 for (let i = 0; i < n; i++) { arr[i] = -arr[i]; } // Find the largest sum of the // subarray with negation of all // array element largestSum = Math.max(largestSum, Kadane(arr, n)); // Return the resultant maximum // value return largestSum; } // Driver Code let arr = [2, -3, 8, -2, 5]; let N = arr.length; document.write(maximumWeight(arr, N)); // This code is contributed by Potta Lokesh </script> |
Output:
88
Time Complexity: O(N)
Auxiliary Space: O(1)
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!
