I have been given been an array arr and the need is to maximize arr[i]*i.
A simple solution given at https://www.geeksforgeeks.org/maximize-sum-arrii is to sort the array and then find the sum. But, how shall I confirm the fact that the resultant sum will be maximum over all the possible answers.
Asked
Active
Viewed 174 times
0
asn
- 2,408
- 5
- 23
- 37
-
This question seems like it's more about a mathematical proof than about programming. – mypetlion Aug 22 '18 at 17:37
-
I want the reason for its greediness. – asn Aug 22 '18 at 17:46
-
2Because `arr[i]*i + arr[i+1]*(i+1) >= arr[i]*(i+1) + arr[i+1]*i` when `arr[i] >= arr[i-1]` – Déjà vu Aug 22 '18 at 17:51
-
See https://stackoverflow.com/questions/44341215/behaviour-of-arri-i-and-i-i-1-statements-in-c-and-c – Paul Maxwell May 11 '23 at 03:09