Maximize product of subarray sum with its maximum element

0 0 7 minutes read

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(N²)
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 element
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 = 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 element
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 = max(largestSum,
                     Kadane(arr, n));
 
    // Return the resultant maximum
    // value
    return largestSum;
}
 
// Driver Code
int 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 approach
 
import 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 element
def 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 element
def 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 Code
if __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 approach
using System;
using System.Collections.Generic;
 
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()
{
    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:

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 zambiatek!