Need help with a question, longest continuous subarray of size <=k

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 :slight_smile:

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;
}
1 Like

sounds promising.