Welcome back, dear reader. So, how is it going? In this video, we will discuss this problem MAX SUBARRAY SUM WITH AT LEAST K ELEMENTS. So, what does this problem say?

**Important Links :** Problem Link, Solution Video

Max Sum Subarray with at least K Elements

So much complexity in software comes from trying to make one thing do two things.

Max Sum Subarray with at least K Elements

Welcome back, dear reader. So, how is it going? In this video, we will discuss this problem MAX SUBARRAY SUM WITH AT LEAST K ELEMENTS. So, what does this problem say?

**Important Links :** Problem Link, Solution Video

Understanding the Problem:

We are given an input array and an integer k. We have to tell the maximum subarray sum from this array under the condition that the size of this subarray should be at least K. Have a look at the example given below:

So, we hope that you have understood the problem completely. We recommend you refer to the question on the portal once for understanding it if you have any doubts regarding it. We also suggest you try to solve this problem on your own first and then refer to the solution video to build your concepts stronger.

Approach:

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

**Space Complexity:** O(1)

Explanation:

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 is making this Problem Complex?

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.

Inefficient Thought Process:

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.

Efficient Thought Process:

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.

Max Subarray sum (with at least K size) at Every Index (Kadane's Algo)

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.

Using The Kadane's Algorithm

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.

import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = scn.nextInt();
}
int k = scn.nextInt();
System.out.println(solution(arr, k));
}
public static int solution(int[] arr, int k) {
int[] maxSum = new int[arr.length];
// use kadane's
maxSum[0] = arr[0];
for(int i = 1 ; i < arr.length; i++) {
maxSum[i] = Math.max(arr[i], maxSum[i - 1] + arr[i]);
}
int sum = 0 ;
for(int i = 0 ; i < k; i++) {
sum += arr[i];
}
int ans = sum;;
for(int i = k ; i < arr.length; i++) {
sum = sum + arr[i] - arr[i - k];
ans = Math.max(ans, sum);
ans = Math.max(ans, sum + maxSum[i - k]);
}
return ans;
}
}

java; true";

The above code is written and explained in the solution video. We recommend you refer to it to clear all your doubts regarding the code if any. Let us now analyze the time and space complexity of the above code.

Analysis

Time Complexity:

The time complexity of the above solution is O(n). We recommend you try to think of the reason yourself as we have already explained the procedure to you and you have already studied and solved some problems based on Kadane's Algorithm too.

Space Complexity:

The space complexity of the above solution is O(1) as we have not used any extra space.

So, dear reader, we have now discussed the complete procedure. We recommend you refer to the complete solution video to understand the process and the code properly. With this, we have completed this problem.

Suggestions:

We suggest that you watch the complete solution video of KADANE'S ALGORITHM to understand its in-depth work. We also suggest that you watch the complete solution video for this problem as well as it will give you the best possible insight into this problem. So, do check out these solution videos and we will meet in the next questions. Till then, Happy Coding!!!