Let’s discuss a interesting problem maximum sum subarray of size k
Given an array of positive integers and a positive number K. Write a code to find the maximum sum subarray of size k.
For example:
|
1 2 3 4 5 |
Example 1: Input: {2, 1, 5, 1, 3, 2}, K = 3 Output: 9 { 5, 1, 3} |
Let’s first understand what all subarrays we can form whose size is 3.
i) First subarray is {2, 1, 5} and it’s sum is 8.
ii) Second subarray is {1, 5, 1} and it’s sum is 7.
iii) Third subarray is {5, 1,3} and it’s sum is 9.
iv) Fourth subarray is {1, 3, 2} and it’s sum is 6.
Out of all these subarrays of size three, the maximum sum subarray is {5, 1, 3} and it’s sum is 9.
We have discussed the problem statement. Let’s think How we can solve this problem? In this tutorial, I am going to discuss two approaches and their time and space complexities to solve this problem.
At the end of this tutorial, I have also mentioned the video tutorial link.
The first approach is brute force approach and the second approach is based on the sliding window approach.
Method 1: Brute Force Approach
The simplest approach is to generate all the subarrays of size k, compute their sum and finally return the maximum sum.
To generate all subarrays of size k, we need two for loops. Outer loop start from 0th index and run till array length minus k. For each index of the array we have to run inner loop to add the next k elements. This way, we will be able to calculate the sum of all k sized subarrays and then return the maximum of all the sums.
The time complexity of this approach is O(n*k) where n is the length of array and k is the length of subarray. And the space complexity is O(1).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
//Find maximum of all subarrays of size k using brute force approach public class MaximumSubarray { public static int bruteForce(int arr[], int k) { //Declare a variable and assigned value 0 int maxSum = 0; //Traverse an array from 0 to n-k for(int i = 0; i <= arr.length-k; i++) { int sum = 0; //Run a loop from i to i+k for(int j = i; j < i+k; j++) { sum = sum + arr[j]; } //Keep track of maximum sum maxSum = Math.max(sum, maxSum); } return maxSum; } public static void main(String[] args) { int[] arr = {2, 1, 5, 1, 3, 2}; int k = 3; int result = bruteForce(arr, k); System.out.println(result); } } |
Maximum Sum Subarray of Size K using Sliding Window – Java Code
The efficient way to solve this problem is by using a sliding window approach.
In our previous approach, we are doing lot of repetitive work by calculating the sum of all the subarrays of size k. Let’s look at the following example:
|
1 2 3 4 5 |
arr = {2, 1, 5, 1, 3, 2}, K = 3 {2, 1, 5} {1, 5, 2} |
There is an overlap between both the subarrays. We are calculating the sum of overlapping part {1, 5} twice. This is were we can use sliding window approach to solve this problem efficiently.
The idea here is to consider each subarray as a sliding window of size k. For calculating, the sum of the next subarray, slide the window by one element. When we slide a window we have to perform following steps –
i) Subtract the element going out of the window.
ii) Add the element getting included in the sliding window.
|
1 2 3 4 5 |
arr = {2, 1, 5, 1, 3, 2}, K = 3 First subarray - {2, 1, 5} Sum = 8 Second subarray - {1, 5, 1} Sum = 7 Subtracted 2 from this window and added 1 Third subarray - {5, 1, 3} Sum = 9 Subtracted 1 from this window and added 3 |
To start with sliding window, we have to declare two variables start and end. Initially, both the pointers point at 0th index. Then, we move end pointer until it is less than or equal to k-1 and keep start pointer as it is.
So, first we compute the sum of first window whose size is equal to k and after that, we increment both start and end pointer by one position. Now the sum of next window can be computed by simply adding the new element and removing the previous element from the current window sum. At each step we also keep track of the maximum sum obtained so far.
The time complexity of this approach is O(n) and it’s space complexity is O(1).
Longest substring without repeating characters
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
//find the maximum of all subarrays of size k using sliding window public class MaximumSubarray { public static int getSum(int arr[], int k) { int start = 0; int sum = 0; int maxSum = 0; for(int end = 0; end < arr.length; end++) { sum = sum + arr[end]; if(end >= k -1) { maxSum = Math.max(sum, maxSum); sum = sum - arr[start]; start++; } } return maxSum; } public static void main(String[] args) { int[] arr = {2, 1, 5, 1, 3, 2}; int k = 3; int result =getSum(arr, k); System.out.println(result); } |
Video Tutorial
Maximum sum subarray of size k video tutorial
