My initial approach was same and you can optimise it further by taking decrement value = minimum(|a[i]-k|,|a[n-1] - a[n-2]|) but still not sufficient:(

We can infer below observations:

**1. We want to maximise Resultant sum after performing possible decrements**

**2. We wan directly add elements <= ***k* and remove them… Further decrease remaining elements by *k* and add *k* to our answer for each of them(since each would be atleast *k*)…Now we have new *g* elements and solve them for *k=0* (for easy calculations I did this modifications)

**3. Now our Aim is to maximise (Resultant value of ***g* elements)

**4. That is we want to maximise ( Greatest element(M1) - Resultant value of remaining (g-1) elements)**

**5. That is we want to minimise (Resultant value of (g-1) elements)**

**6. This would have two cases:**

… **I)… If second highest element(M2) is greater than Sum of remaining (g-2) elements then their minimum Resultant value = M2 - Sum of(g-2 elements)**

…**II)… Else this (g-1)elements would cancel out each other and either 0 or 1 would remain depending on their sum is even or odd(since we can decrement only in pairs)**

Thus we can solve it with Time Complexity : O(n)

Here is my

```
[1]
I am not sure it would definitely work but it passed all the random cases I tried...your suggestions are most welcomed...Also if any confusion you are free to discuss :)
[1]: http://jdoodle.com/a/KvV
```