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
= (Zarr[1], Zarr[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.,
{71, 73} = {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

Time Complexity: O(N^{2})
Auxiliary Space: O(1)