### PROBLEM LINK

### CONTEST PANEL

**Author:** neo1tech9_7

### PREREQUISITES

Basic Math

### DIFFICULTY

EASY

### PROBLEM

An array with N elements *(both positive and negative)* is given, a term happiness is defined as the sum of all elements of a selected subset from given array multiplied by the number of elements in it. A element from the array can be taken in a subset only once and all elements must appear in some subset, find the **maximum** value of happiness possible.

### EXPLANATION

*Complexity:* **O(nlogn)**

#### Subtask 1:

This subtask consists of all negative array elements, so to maximise the happiness we select a subset of 1 element for all array elements i.e simply the summation of all array elements.

#### Subtask 2:

As anyone would guess, to maximise happiness we need to select a subset whose * sum(number of terms)** is the greatest.

To start off with my solution what I do is pre-calculate the sum of subset of all positive numbers and subset of all negative numbers and take note of **count of positive numbers and zeroes** and store absolute values of negative numbers in an array or vector and sort it in ascending fashion.

So for our initially selected subset (set of all non-negative values) we are at **happiness=(positive sum)*(count of positive numbers and zeroes)**.

for example:

A = {10,5,-1,-2,-3}

starting subset = {10,5}

starting happiness = (10+5)*(2) = 30

negative vector = {1,2,3} (Recall that we took absolute values)

**Note: We are adding absolute values of all negative numbers and will be testing whether the number will be appearing in the subset from smallest absolute value to greatest.**

Find the proof for this greedy algorithm in the answer by @hikarico.

Note that this selected initial subset is dynamic and we will **check whether the addition of negative numbers (from smallest absolute value to the greatest) will result in happiness greater than what we have at present** and if addition of negative numbers in the selected subset results in a greater happiness we insert that negative value in the subset, refer the pseudocode below for clarification.

```
accumulator = subset length
sum = subset sum
ans = accumulator*sum
for(i from 0 to length of negative array){
if((sum-negative[i])*(accumulator+1) greater than ans){
ans = (sum-negative[i])*(accumulator+1);
sum-=negative[i];
accumulator++;
}
}
```

After you’ve done this you are at a situation where no addition of negative numbers in the subset will result in greater happiness so what we do is *make subsets of one element* for all the remaining negative elements not in any subset and thus subtract all the remaining negative numbers from happiness.

Thus this is how we arrive at max happiness possible.

Do feel free to share your approach and feel free to comment if you have any doubt

### SOLUTION

My AC

**Execution Time:** 0.1 s

**Memory:** 3.3M