In the editorial they say,
It can be noticed that the largest and first value will always be sum of all the elements as it is given that all elements are positive integers. It means the sum is corresponding to the subarray [1toN] inclusively. Now, we have taken up the range 1…N1…N and we can see that the next possible largest sum will be the maximum of sum of range 2…N and range 1…N−1. Let us assume that the second largest is obtained from the range 1…N−1. Then, the third largest sum will be maximum of sum of range 2…N ( previous range left ), range 2…N−1 and range 1…N−2 ( new ranges ). The above procedure can be run K times to find the largest K values.
Q-1. Do i have to sort the array to understand this logic first…??
Q-2. If i do sorting , then how is this possible that 2nd largest sum will lie in range [1…N-1] , it should always be int the range [2…N] …?? (If i not consider the duplicates)…
Q-3 in editorial they are using set container class. How will it handle duplicate values ??