Best order to maximise the value

By Ann Roberts On Apr 6, 2023

Given, an array arr[] of N integers, the task is to select some integers from this array arr[] and arrange them in another array brr[], such that the sum of brr[i]*(i+1) for every index in array brr is maximum. Find out the maximum possible such value for a given array arr.

Input: N = 5, arr[] = {-1, -8, 0, 5, -9}
Output: 14
Explanation: By selecting -1, 0, and 5 we will get the maximum possible value.(-1*1 + 0*2 + 5*3 = 14)

Input: N = 3, arr[] = {-1, -8, -9}
Output: 0
Explanation: Since all the numbers are negative it’s better not to select any number.

Approach: To solve the problem follow the below idea:

The problem can be solved using a greedy approach. The intuition behind the greedy approach is that the maximum value is obtained by selecting the largest number first, and the smallest number last. By sorting the array in decreasing order, we can ensure that we have the largest number at first, and thus maximize the value.

Steps that were to follow the above approach:

First, we sort the input array in decreasing order.
Then, we iterate over the array and calculate the prefix sums of the elements, adding each prefix sum to the result as long as it remains non-negative.
If the prefix sum becomes negative at any point, we stop the iteration and return the current result.
By stopping the iteration as soon as the prefix sum becomes negative, we can ensure that we don’t select any numbers that have a net negative contribution to the total value. This allows us to obtain the maximum value.

Below is the code to implement the above approach:

Python3

def bestOrder(arr, N):

arr.sort(reverse = True)

prefixsum, result = 0, 0

for i in range(N):

prefixsum += arr[i]

if prefixsum < 0:

break

result += prefixsum

return result

N = 5

arr = [-1, -8, 0, 5, -9]

print(bestOrder(arr, N))

Time Complexity: O(N*logN), where N is the length of the array.
Auxiliary Space: O(1), as we are not using any extra space.