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.

Java

  

import java.util.*;

  

class GFG

  

    

    public static void main(String[] args)

    

        long[] arr = 500, 100, 400, 560, 876 ;

        int N = arr.length;

        long Z = 1000;

  

        

        System.out.println(Max_Product(N, arr, Z));

    

  

    

    

    static long Max_Product(int n, long[] arr, long Z)

    

        

        long product = Long.MIN_VALUE;

  

        

        Arrays.sort(arr);

  

        

        long sum1 = 0;

  

        

        

        long X = Integer.MIN_VALUE;

  

        

        

        long Y = Integer.MAX_VALUE;

  

        

        

        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);

    

Time Complexity: O(N2)
Auxiliary Space: O(1)