Doubt in KSUM editorial

general
1

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 ??

2

No, the problem demands contiguous subarrays.
So, you cannot change the structure(sequence) of numbers in the array because changing the structure will not lead to contiguous subarray sum.

3

A-1. You can sort the array where you’re storing the sum but not the original array.
A-2. sort the array sum[1…k] from 2 to n(n+1)/2.
Example - input : 3 4
array : 2 4 3
Sub arrays :{2,4,3},{2,4},{2},{4,3},{4},{3}
Then the sums are 9,6,2,7,4,3.
You can sort from 6 to 3 which will give 7,6,4,3,2
but if you sort the original array the sub arrays will be {4,2},{2,3},{4,3,2},{4},{3},{2} which will change the sum 6,5,9,4,3,2 giving you wrong output.
I hope this helps…

2 Likes