Time Complexity: O(n) where n is the size of the input array

Space Complexity: O(1)

Dear reader, we recommend you refer to the KADANE'S ALGORITHM VIDEO once, even if you have watched it as you need to have an in-depth knowledge of Kadane's Algorithm to solve this problem.

First of all, let us see how many subarrays with at least k elements can we have at any particular position. Have a look at the image shown below:

In the given array, before index 3, there is no subarray with at least 4 elements (k=4). At index=3, we have exactly one subarray and that is exactly of size=4. At index=5, we have two subarrays, one of size 4 and the other of size=5.

Similarly, at index=6, we will have 3 subarrays, one of size=4, the other of size=5, and the third one of size=6. So, at index=6, we have 3 subarrays that have at least 4 elements.

So, we have a lot of subarrays that have at least K size at every index starting from k-1 to n-1. So, we first need to have the best subarray (i.e. max sum subarray) at every index (with size at least K), then only, we will be able to compare it with other subarrays at different indices to get the maximum subarray sum of a subarray with at least K size.

What do we want to say? See, in img-4, we can see that we have 3 different subarrays with at least K size at index 5. Now, if we know the subarray with maximum sum at index 5 (i.e. the current best in Kadane's Algorithm), then only we can move forward and compare it with the current maximum value (overall best in Kadane's Algorithm) of the subarray that we have (Please refer to Kadane's Algorithm if you are having trouble in understanding this part).

Now, there are two ways to do that.

The first way is that we have all the subarray sums with at least k size at any index, we compare them, and get the maximum out of them and then compare the current best (max) sum with the overall best sum.

The second approach will not calculate the sum of all the subarrays with at least k size at every index. In this approach, we only generate the best (max) sum subarray with at least k size directly at every index and continue with the normal way in Kadane's Algorithm.

Now, the question arises: How will we generate the max subarray sum at every index that has at least K size directly without comparing every subarray sum at that index with at least K size?

Well, we will use Kadane's Algorithm to do that too. How? Let us see it.

Have a look at the diagram given below:

Let us say we are at index 6. 4 subarrays have at least size=4 at index 6. So, we want to find the maximum subarray sum out of them so that we don't have to calculate the sum of every subarray.

Let us first find the sum of the window of size K at index 6 as shown in the image below. If we know the sum of the window of size=k at index 6, the maximum subarray sum of at least size=K can be calculated if we know the max subarray sum before index 6.

We will add this sum to the sum of the window of size=k and we will get the maximum subarray sum of the subarray of size at least K at index 6.

So, to calculate the current best (max) sum at any index, we need to calculate the sum of the window of size=4 and then add the best (max) sum till the window (before it) to it.

So, if we want to calculate the max sum subarray of at least size=K at index 6, first calculate arr[6] + arr[5] + arr[4] + arr[3]. After this, add the max sum subarray till index 2 to this and we will get the answer.

Note: Please note that the max sum subarray that we are adding to the sum of the window of size K is not the max sum subarray with at least size=K. It is just the overall max sum subarray that we used to get from Kadane's algorithm. This is because the problem of having at least size=K has already been resolved by taking the sum of the window of size K. Now, we want to have the max sum which will be given to us by Kadane's Algorithm.

We recommend you refer to the solution video to understand the complete procedure that we have discussed here. Now, we know what we have to do. We will run Kadane's Algorithm for a few elements now to see if the method that we have devised above is working fine or not.

Consider the following array given below:

Now, dear reader, as we have already asked you to see Kadane's Algorithm video, you know that we used to calculate the current best and the overall best at every index in Kadane's Algorithm.

So, we want you to calculate the current best and overall best till index 3 yourself and match your answer with the diagram shown below:

You would have understood the above diagram completely if you had watched Kadane's Algorithm video or watched this solution video. So, since we took k=4 in our example, this is the first index where we will have a window of at least size=4. So, we take this window of size 4 and calculate the sum of the first 4 elements i.e. the sum of this window.

So, we hope that you understood the above step completely. Now, let us move the window forward. See, the window is moved forward just virtually. In reality, we will move the index "I" forward, add the arr[i] to the previous window sum i.e. -1, and subtract the last element i.e. arr[i-k-1]=2 from the window sum.

Now, at index 4, we have a subarray of size 4 and also a subarray of size 5. So, what should be chosen?

As discussed in the procedure above, we will add the best subarray sum till index 0 to the window sum as shown in the image below:

So, as you can see, at this point, we have 3 different maximums. The current maximum subarray sum is 6 and there is only one element in that subarray and i.e. 6.

The current maximum subarray sum is also 6 with the previous elements {2,3,1} as the subarray.

The current maximum subarray sum with at least k=4 elements is 5 with 5 elements {2,3,1,-7,6} as the subarray.

We hope that this step has cleared most of your doubts. Let us perform one more iteration and see what we get.

So, here the current max sum is 1 and there are 2 elements in the array {6,-5}.

The overall best is also not changed because it is still greater than the current best.

The overall best with at least size=k=4 is also not changed because the sum of the window and best sum before it when summed together is less than the previous value i.e. 5.

So, in this way, we will proceed with the procedure and we will not have to iterate again and again to calculate the sum of different subarrays of at least length=K at any particular index.

We recommend you refer to the solution video to understand this concept and the procedure completely and understand one complete run of Kadane's Algorithm on an array.

Now that we have understood the complete procedure, let us write the code for the same.