the exact question is further attached as an image.
constraints: N<=10^5, K<=N
please help.
this is an extremely popular problem, also called “maximum sum subarray problem” or “maximum segment sum problem”.
Because this is so popular, you will be able to find a lot of guides online.
Here is a YouTube guide: Maximum Subarray - Amazon Coding Interview Question - Leetcode 53 - Python - YouTube
Here is a written guide: Search the subsegment with the maximum/minimum sum - Algorithms for Competitive Programming
The YouTube guide shows 1 approach working in O(n), the written guide shows 2 approaches working in O(n) and some alternatives.
Nopes, the above 2 links both give a reference to Kadane’s algorithm which is maximum subarray sum possible, but the question I posted is slight modification, it has a constraint K, where our window has to be of size <=K , Hopefully I was clear
ups, I skipped over the K constraint. But you can adjust both algorithms I have linked.
First algorithm from cp-algo (I linked above), that does not yet pay attention to K. (I extracted the sum out of the for-loop and created a proper prefixSum array to make it easier to understand and rewrote it in Java)
//runs in O(n) time complexity
public static long calcSum(int n, long[] pnl){
long[] prefixSum = new long[n+1];
for (int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i-1] + pnl[i-1];
// pnl = {-3, 4, 3, -2, 2, 5}
// prefixSum = {0, -3, 1, 4, 2, 4, 9}
long ans = pnl[0];
long minSum = 0;
for (int i = 0; i < n; i++) {
ans = max(ans, prefixSum[i+1] - minSum);
minSum = min(minSum, prefixSum[i+1]);
}
return ans;
}
Note (important): the minSum value is the minimum prefixSum value until i. If we want to limit k, the minSum is only allowed to store the minimum prefixSum value between i-k+1 and i (inclusive), with i-k+1 not being smaller than 0.
I am using Java in this example. The way to do this is Java is to not store min_sum inside an int, but inside a proper datastructure. In this case a TreeMap, which is equivalent to the std::map in C++. we can lookup the smallest value inside a TreeMap in O(1), but inserting/deleting runs in O(log n). By storing all prefixSum values, we can limit k by always deleting old ones, those out of our range.
//runs in O(n log n) time complexity
public static long calcSum(int n, long[] pnl, int k){
long[] prefixSum = new long[n+1];
for (int i = 1; i <= n; i++) prefixSum[i] = prefixSum[i-1] + pnl[i-1];
// pnl = {-3, 4, 3, -2, 2, 5}
// prefixSum = {0, -3, 1, 4, 2, 4, 9}
long ans = pnl[0];
TreeMap<Long, Integer> minSums = new TreeMap<>(); //stores prefixSum values in key and the amount in value
for (int i = 0; i < n; i++) {
// next 4 lines assert that minSums always contains the prefixSum values between i-k+1 and i (inclusive), with i-k+1 not being smaller than 0.
minSums.put(prefixSum[i], minSums.getOrDefault(prefixSum[i], 0) + 1);
if(i >= k){ //i >= k means we have to remove the 'oldest' prefixSum from our map
minSums.put(prefixSum[i-k], minSums.get(prefixSum[i-k])-1);
if(minSums.get(prefixSum[i-k]) <= 0) minSums.remove(prefixSum[i-k]);
}
//minSums.firstKey() returns the min key value in O(1)
ans = max(ans, prefixSum[i+1] - minSums.firstKey());
}
return ans;
}
sounds promising.