PROBLEM LINK:
Author: Sunny Aggarwal
Tester: Sergey Kulik
Editorialist: Sunny Aggarwal
DIFFICULTY:
Easy
PREREQUISITES:
Sorting, Greedy, Data Structure, Implementation.
PROBLEM STATEMENT:
Given an array A containing N positive integers and an integer K. We are asked to report the largest K values from the list of sums of all possible subarrays of array A.
EXPLANATION:
Subtask 1
Listing sums of all the possible subarrays of A and finding the largest K values will be enough to pass this subtask.
C++ Code
#define ll long long
void solve(int N, int K, int *arr) {
vector sum;
for(int i=1;i<=n;i++) {
long long int s = 0;
for(int j=i;j<=n;j++) {
s += arr[j];
sum.push_back(s);
}
}
sort(sum.rbegin(), sum.rend());
for(int i=0; i<=K-1; i++) cout << sum[i] << " ";
cout << "\n";
}
Time Complexity
O((\frac{N \times (N+1)}{2})) \times \log{\frac{N \times (N+1)}{2}})
Note
Although the above solution will get passed on first subtask but we can have slight better complexity by maintaining a priority queue for the first K elements instead of sorting all the sums.
Subtask 2
It is easy to see that the above solution will time out for this subtask.
Then, how to approach it ?
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 [1 to N] inclusively. Now, we have taken up the range 1...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.
How to implement above idea ?
Let us maintain a priority queue S ( set can also be used in C++ ). So, whenever we are taking the sum of a range say [L to R] from S, we can simply insert 2 new values to S i.e sum of range [L+1 to R] and [L to R-1] if L != R. Note that along with sum of range we are also maintaining the indices i.e L and R denoting that range in our priority queue.
C++ Code
#define ll long long
void solve(int N, int K, int *arr) {
set<pair<ll,pair> S;
long long int prefix_sum[N+1];
for(int i=1;i<=n;i++) {
prefix_sum[i] = prefix_sum[i-1] + arr[i];
}
S.insert({prefix_sum[N], {1, N}});
while( K -- && !S.empty() ) {
pair<ll,pair> top = *S.begin();
S.erase( top );
long long int sum;
int L, R;
sum = top.first;
L = top.second.first;
R = top.second.second;
cout << sum <<" ";
if( L != R ) {
S.insert({sum-arr[L], {L+1, R}});
S.insert({sum-arr[R], {L, R-1}});
}
}
}
TIME COMPLEXITY:
O(K \times \log{K})
AUTHOR’S AND TESTER’S SOLUTION:
Author’s solution can be found here.
Tester’s solution can be found here.