Maximize the Product of Sum by converting Array elements into given two types - Coding

Given an array of positive integer arr[] of length N and an integer Z, (Z > arr[i] for all 0 ? i ? N – 1). Each integer of the array can be converted into the following two types:

Keep it unchanged
Change it to Z – arr[i].

The task is to maximize the product of the sum of these two types of elements.

Note: There should be present at least one element of each type.

Examples:

Input: N = 5, arr[] = {500, 100, 400, 560, 876}, Z = 1000
Output: 290400
Explanation: arr[] = {500, 100, 400, 560, 876}
Convert elements present at indices 0, 3 and 4 to first type = (500, 560, 876)
Convert elements present at indices 1 and 2 to second type
= (Z-arr[1], Z-arr[2]) = (1000 – 100, 1000 – 400) = (900, 600)
Sum of all first type elements = 500+560+876 = 1936
Sum of all second type elements = 900 + 600 = 1500
Product of each type sum = 1936*1500 = 290400.
Which is maximum possible for this case.

Input: N = 4, arr[] = {1, 4, 6, 3}, Z = 7
Output: 100
Explanation: Change the 1st and last element to 2nd type, i.e.,
{7-1, 7-3} = {6, 4}. The sum is (6 + 4) = 10.
Keep the 2nd and third element as it is. Their sum = (4 + 6) = 10 .
Product is 10*10 = 100. This is the maximum product possible.

Approach: The problem can be solved using Sorting based on the following idea:

The idea is to sort the arr[] in decreasing order, Calculate product of all possible combinations of the types. Obtain maximum product among all combinations.

Illustration:

Input: N = 4, arr[] = {1, 4, 6, 3}, Z = 7

After sorting arr[] in decreasing order = {6, 4, 3, 1}

Now we have 3 possible combinations for choosing all elements as first or second type:

1 of first type, 3 of second type

2 of first type, 2 of second type

3 of first type, 1 of second type

Let’s see the product and sum at each combination for decreasing ordered arr[]:

Choosing first element as first type and next 3 elements as second type:

Sum of first type elements = 6

Sum of second type elements = ((7 – 4)+(7 – 3)+(7 – 1))= 13

Product of first and second = 6 * 13 = 78

Choosing first two elements as first type and last 2 elements as second type:

Sum of first type elements = 6 + 4 = 10

Sum of second type elements = (7 – 3)+(7 – 1))= 10

Product of first and second types = 10 * 10 = 100

Choosing first three elements as first type and last element as second type:

Sum of first type elements = 6 + 4 + 3 = 13

Sum of second type elements = (7 – 1)) = 6

Product of first and second types = 13 * 6 = 78

As we can clearly see that 2nd combination has maximum value of product.Therefore, output for this case is :

Maximum Product: 100

Follow the steps to solve the problem:

Sort the input array arr[].
Traverse from the end of the array to calculate the product for all possible combinations:
- Consider all the element till index i as first type, and the suffix elements as second type.
- Calculate the product of this combination.
- Update the maximum product accordingly.
Print the maximum product obtained.

Below is the implementation of the above approach.

C++

// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to obtain maximum product
// along with sum of X and Y
long Max_Product(int n, vector<long> arr, long Z)
{
    // Variable to store maximum product
    long product = INT_MIN;
 
    // Sorting arr[]
    sort(arr.begin(), arr.end());
 
    // Variable to Hold sum of first type
    long sum1 = 0;
 
    // Variable to hold Maximum value
    // of first type sum
    long X = INT_MIN;
 
    // Variable to hold Maximum value
    // of second type sum
    long Y = INT_MAX;
 
    // Loop for iterating on sorted arr[]
    // from right to left for decreasing order
    for (int i = n - 1; i > 0; i--)
    {
        sum1 += arr[i];
        long sum2 = 0;
        for (int j = i - 1; j >= 0; j--)
        {
            sum2 = sum2 + (Z - arr[j]);
        }
        if (sum1 * sum2 > product)
        {
            product = sum1 * sum2;
            X = sum1;
            Y = sum2;
        }
    }
 
    return (product);
}
// Driver code
int main()
{
    vector<long> arr = {500, 100, 400, 560, 876};
    int N = arr.size();
    long Z = 1000;
 
    // Function call
    cout << (Max_Product(N, arr, Z));
}
// This code is contributed by Potta Lokesh

Java

// Java code to implement the approach
 
import java.util.*;
 
class GFG {
 
    // Driver code
    public static void main(String[] args)
    {
        long[] arr = { 500, 100, 400, 560, 876 };
        int N = arr.length;
        long Z = 1000;
 
        // Function call
        System.out.println(Max_Product(N, arr, Z));
    }
 
    // Function to obtain maximum product
    // along with sum of X and Y
    static long Max_Product(int n, long[] arr, long Z)
    {
        // Variable to store maximum product
        long product = Long.MIN_VALUE;
 
        // Sorting arr[]
        Arrays.sort(arr);
 
        // Variable to Hold sum of first type
        long sum1 = 0;
 
        // Variable to hold Maximum value
        // of first type sum
        long X = Integer.MIN_VALUE;
 
        // Variable to hold Maximum value
        // of second type sum
        long Y = Integer.MAX_VALUE;
 
        // Loop for iterating on sorted arr[]
        // from right to left for decreasing order
        for (int i = n - 1; i > 0; i--) {
            sum1 += arr[i];
            long sum2 = 0;
            for (int j = i - 1; j >= 0; j--) {
                sum2 = sum2 + (Z - arr[j]);
            }
            if (sum1 * sum2 > product) {
                product = sum1 * sum2;
                X = sum1;
                Y = sum2;
            }
        }
 
        return (product);
    }
}

Python3

# Python code to implement the approach
 
# Function to obtain maximum product
# along with sum of X and Y
def Max_Product(n, arr, Z):
   
    # Variable to store maximum product
    product = -10000000000000000000000
     
    # Sorting arr[]
    arr.sort()
     
    # Variable to Hold sum of first type
    sum1 = 0
 
    # Variable to hold Maximum value
    # of first type sum
    X = -10000000000000000000000
 
    # Variable to hold Maximum value
    # of second type sum
    Y = 100000000000000000000000
 
    # Loop for iterating on sorted arr[]
    # from right to left for decreasing order
    for i in range(n-1, 0, -1):
        sum1 += arr[i]
        sum2 = 0
        for j in range(i-1, -1, -1):
            sum2 = sum2 + (Z - arr[j])
            if (sum1 * sum2 > product):
                product = sum1 * sum2
                X = sum1
                Y = sum2
 
    return product
 
# Driver code
if __name__ == "__main__":
    arr = [500, 100, 400, 560, 876]
    N = len(arr)
    Z = 1000
     
    # Function call
    print(Max_Product(N, arr, Z))
 
# This code is contributed by Rohit Pradhan

C#

// C# code to implement the approach
 
using System;
 
public class GFG{
 
  static public void Main (){
 
    // Code
    long[] arr = { 500, 100, 400, 560, 876 };
    int N = arr.Length;
    long Z = 1000;
 
    // Function call
    Console.WriteLine(Max_Product(N, arr, Z));
  }
 
  // Function to obtain maximum product
  // along with sum of X and Y
  static long Max_Product(int n, long[] arr, long Z)
  {
    #pragma warning disable 219
      // Variable to store maximum product
      long product = Int64.MinValue;
 
    // Sorting arr[]
    Array.Sort(arr);
 
    // Variable to Hold sum of first type
    long sum1 = 0;
 
    // Variable to hold Maximum value
    // of first type sum
    long X = Int32.MinValue;
 
    // Variable to hold Maximum value
    // of second type sum
    long Y = Int32.MaxValue;
 
    // Loop for iterating on sorted arr[]
    // from right to left for decreasing order
    for (int i = n - 1; i > 0; i--) {
      sum1 += arr[i];
      long sum2 = 0;
      for (int j = i - 1; j >= 0; j--) {
        sum2 = sum2 + (Z - arr[j]);
      }
      if (sum1 * sum2 > product) {
        product = sum1 * sum2;
        X = sum1;
        Y = sum2;
      }
    }
 
    return product;
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

<script>
// JS code to implement the approach
 
    // Function to obtain maximum product
    // along with sum of X and Y
    function Max_Product(n, arr, Z)
    {
        // Variable to store maximum product
        let product = Number.MIN_VALUE;
 
        // Sorting arr[]
        arr.sort();
 
        // Variable to Hold sum of first type
        let sum1 = 0;
 
        // Variable to hold Maximum value
        // of first type sum
        let X =Number.MIN_VALUE;
 
        // Variable to hold Maximum value
        // of second type sum
        let Y = Number.MAX_VALUE;
 
        // Loop for iterating on sorted arr[]
        // from right to left for decreasing order
        for (let i = n - 1; i > 0; i--) {
            sum1 += arr[i];
            let sum2 = 0;
            for (let j = i - 1; j >= 0; j--) {
                sum2 = sum2 + (Z - arr[j]);
            }
            if (sum1 * sum2 > product) {
                product = sum1 * sum2;
                X = sum1;
                Y = sum2;
            }
        }
 
        return (product);
    }
 
// Driver code
 
        let arr = [ 500, 100, 400, 560, 876 ];
        let N = arr.length;
        let Z = 1000;
 
        // Function call
        document.write(Max_Product(N, arr, Z));
 
// This code is contributed by sanjoy_62.
</script>

Output

Time Complexity: O(N*N+NlogN)
Auxiliary Space: O(1)

Reffered: https://www.geeksforgeeks.org

Arrays

Related
Minimize cost to buy N elements using given cost Array
Split array into K Subarrays to minimize sum of difference between min and max
Create Array of distinct elements where odd indexed elements are multiple of left neighbour
Maximum prefix sum which is equal to suffix sum such that prefix and suffix do not overlap
Minimum time to fulfil all orders

Type:	Geek
Category:	Coding
Sub Category:	Tutorial
Uploaded by:	Admin
Views:	11