Find maximum sum subarray of given size
The problem is to find the maximum sum subarray of a given size 'k' within an array. A subarray is a contiguous segment of the array.
Problem Statement and Description
Given an array of integers and a positive integer 'k', the task is to write a program that finds and prints the maximum sum of a subarray of size 'k'. The program should also indicate the indices of the subarray that yields the maximum sum.
Example
Consider the following examples of arrays and 'k' values:
-
Array:
[6, 8, 1, -3, 15, 5, -4]
, k = 3- The maximum sum subarray of size 3 is
[15, 5, -4]
, and the sum is15 + 5 + (-4) = 16
.
- The maximum sum subarray of size 3 is
-
Array:
[6, 10, -7, 2, 9, -2, 5, 1]
, k = 4- The maximum sum subarray of size 4 is
[10, -7, 2, 9]
, and the sum is10 + (-7) + 2 + 9 = 14
.
- The maximum sum subarray of size 4 is
Idea to Solve the Problem
To solve this problem, we can use a sliding window approach. Here are the steps:
- Initialize two pointers,
start
andlast
, both set to0
, and a variablesum
to store the sum of the current subarray. - Iterate through the array:
- If the current index is less than 'k', add the element to the
sum
. - Otherwise, remove the element at
arr[i - k]
from thesum
and add the current element to thesum
. - If the current
sum
is greater than the previous maximum sum, update thestart
andlast
pointers and thesum
.
- If the current index is less than 'k', add the element to the
- After the loop, print the original array, the maximum sum, and the indices of the subarray.
Standard Pseudocode
Here's a high-level pseudocode representation of the algorithm to find the maximum sum subarray of a given size 'k':
FindMaxKSubarray(arr, size, k):
Initialize start to 0
Initialize last to k - 1
Initialize sum to 0
Initialize result to 0
For i from 0 to size - 1:
If i < k:
sum += arr[i]
result = sum
Else:
sum = sum - arr[i - k] + arr[i]
If sum > result:
start = i - (k - 1)
last = i
result = sum
Display the array elements
Display "Max sum subarray of given length [", k, "] is", result, "are exist between index [", start, "] to [", last, "]."
Algorithm Explanation
- Initialize
start
andlast
to 0,sum
to 0, andresult
to 0. - Iterate through the array using a loop from
0
tosize - 1
. - If
i
is less thank
, add the element atarr[i]
to thesum
and updateresult
. - Otherwise, remove the element at
arr[i - k]
from thesum
and add the element atarr[i]
to thesum
. - If the current
sum
is greater thanresult
, updatestart
,last
, andresult
. - Display the array elements and the result.
Code Solution
//C Program
//Find maximum sum subarray of given size
#include <stdio.h>
//Print array element
void print_array(int arr[], int size)
{
printf("\n");
for (int i = 0; i < size; i++)
{
printf(" %d ", arr[i]);
}
}
//Find the maximum sum subarray of given length k
//Assuming that the length of subarray k is greater than 2
void max_k_subarray(int arr[], int size, int k)
{
if (size < 2 || size < k || k < 2)
{
//When find invalid inputs
//Here can be three possibilities
//When array contains less than 2 elements, so subarray is not possible
//when array size are less than given subarray length
//Last is when given subarray have less than 2 elements
return;
}
//Set the initial resultant of sub array
int start = 0, last = k - 1;
int sum = 0;
int result = 0;
for (int i = 0; i < size; ++i)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//When possible of more than 1 subarray of given length k
//Remove first element of pervious subarray
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
}
//Display array elements
print_array(arr, size);
//Display result
printf("\nMax sum subarray of given length [%d] is %d, are exist between index [%d] to [%d].\n", k, sum, start, last);
}
int main()
{
// Define the array elements
int arr1[] = {6,8,1,-3,15,5,-4};
// Find the size
int size = sizeof(arr1)/sizeof(arr1[0]);
max_k_subarray(arr1,size,3);
// Define the array elements
int arr2[] ={6,10,-7,2,9,-2,5,1};
// Find the size
size = sizeof(arr2)/sizeof(arr2[0]);
max_k_subarray(arr2,size,4);
return 0;
}
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
Java Program
Find maximum sum subarray of given size
*/
class MyArray
{
//Print array element
void print_array(int[] arr, int size)
{
System.out.print("\n");
for (int i = 0; i < size; i++)
{
System.out.print(" " + arr[i] + " ");
}
}
//Find the maximum sum subarray of given length k
//Assuming that the length of subarray k is greater than 2
void max_k_subarray(int[] arr, int size, int k)
{
if (size < 2 || size < k || k < 2)
{
//When find invalid inputs
//Here can be three possibilities
//When array contains less than 2 elements, so subarray is not possible
//when array size are less than given subarray length
//Last is when given subarray have less than 2 elements
return;
}
//Set the initial resultant of sub array
int start = 0, last = k - 1;
int sum = 0;
int result = 0;
for (int i = 0; i < size; ++i)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//When possible of more than 1 subarray of given length k
//Remove first element of pervious subarray
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
}
//Display array elements
print_array(arr, size);
System.out.print("\nMax sum subarray of given length [" + k + "] is " + sum + ", are exist between index [" + start + "] to [" + last + "].\n");
}
public static void main(String[] args)
{
MyArray obj = new MyArray();
// Define the array elements
int[] arr1 = {
6,
8,
1,
-3,
15,
5,
-4
};
// Find the size
int size = arr1.length;
obj.max_k_subarray(arr1, size, 3);
// Define the array elements
int[] arr2 = {
6,
10,
-7,
2,
9,
-2,
5,
1
};
// Find the size
size = arr2.length;
obj.max_k_subarray(arr2, size, 4);
}
}
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
C++ Program
Find maximum sum subarray of given size
*/
#include<iostream>
using namespace std;
class MyArray
{
public:
//Print array element
void print_array(int arr[], int size)
{
cout << "\n";
for (int i = 0; i < size; i++)
{
cout << " " << arr[i] << " ";
}
}
//Find the maximum sum subarray of given length k
//Assuming that the length of subarray k is greater than 2
void max_k_subarray(int arr[], int size, int k)
{
if (size < 2 || size < k || k < 2)
{
//When find invalid inputs
//Here can be three possibilities
//When array contains less than 2 elements, so subarray is not possible
//when array size are less than given subarray length
//Last is when given subarray have less than 2 elements
return;
}
//Set the initial resultant of sub array
int start = 0, last = k - 1;
int sum = 0;
int result = 0;
for (int i = 0; i < size; ++i)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//When possible of more than 1 subarray of given length k
//Remove first element of pervious subarray
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
}
//Display array elements
this->print_array(arr, size);
cout << "\nMax sum subarray of given length [" << k << "] is " << sum << ", are exist between index [" << start << "] to [" << last << "].\n";
}
};
int main()
{
MyArray obj;
int arr1[] = {
6,
8,
1,
-3,
15,
5,
-4
};
// Find the size
int size = sizeof(arr1) / sizeof(arr1[0]);
obj.max_k_subarray(arr1, size, 3);
int arr2[] = {
6,
10,
-7,
2,
9,
-2,
5,
1
};
// Find the size
size = sizeof(arr2) / sizeof(arr2[0]);
obj.max_k_subarray(arr2, size, 4);
return 0;
}
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
C# Program
Find maximum sum subarray of given size
*/
using System;
class MyArray
{
//Print array element
void print_array(int[] arr, int size)
{
Console.Write("\n");
for (int i = 0; i < size; i++)
{
Console.Write(" " + arr[i] + " ");
}
}
//Assuming that the length of subarray k is greater than 2
void max_k_subarray(int[] arr, int size, int k)
{
if (size < 2 || size < k || k < 2)
{
return;
}
//Set the initial resultant of sub array
int start = 0, last = k - 1;
int sum = 0;
int result = 0;
for (int i = 0; i < size; i++)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//Remove first element of pervious subarray
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
}
//Display array elements
print_array(arr, size);
Console.Write("\nMax sum subarray of given length [" + k + "] is " + sum + ", are exist between index [" + start + "] to [" + last + "].\n");
}
public static void Main(String[] args)
{
MyArray obj = new MyArray();
int[] arr1 = {
6,
8,
1,
-3,
15,
5,
-4
};
// Find the size
int size = arr1.Length;
obj.max_k_subarray(arr1, size, 3);
int[] arr2 = {
6,
10,
-7,
2,
9,
-2,
5,
1
};
// Find the size
size = arr2.Length;
obj.max_k_subarray(arr2, size, 4);
}
}
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
<?php
/*
Php Program
Find maximum sum subarray of given size
*/
class MyArray
{
//Print array element
function print_array( $arr, $size)
{
echo "\n";
for ($i = 0; $i < $size; $i++)
{
echo " ". $arr[$i] ." ";
}
}
//Assuming that the length of subarray k is greater than 2
function max_k_subarray( & $arr, $size, $k)
{
if ($size < 2 || $size < $k || $k < 2)
{
return;
}
//Set the initial resultant of sub array
$start = 0;
$last = $k - 1;
$sum = 0;
$result = 0;
for ($i = 0; $i < $size; ++$i)
{
if ($k > $i)
{
//Get the first subarray sum
$result += $arr[$i];
$sum = $result;
}
else
{
//Remove first element of pervious subarray
$result = $result - $arr[$i - $k];
//Add current element
$result = $result + $arr[$i];
if ($result > $sum)
{
//Modify the resultant index
$start = $i - ($k - 1);
$last = $i;
//Set new max sum
$sum = $result;
}
}
}
//Display array elements
$this->print_array($arr, $size);
echo "\nMax sum subarray of given length [". $k ."] is ". $sum .", are exist between index [". $start ."] to [". $last ."].\n";
}
}
function main()
{
$obj = new MyArray();
// Define the array elements
$arr1 = array(6, 8, 1, -3, 15, 5, -4);
// Find the size
$size = count($arr1);
$obj->max_k_subarray($arr1, $size, 3);
// Define the array elements
$arr2 = array(6, 10, -7, 2, 9, -2, 5, 1);
// Find the size
$size = count($arr2);
$obj->max_k_subarray($arr2, $size, 4);
}
main();
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
Node Js Program
Find maximum sum subarray of given size
*/
class MyArray
{
//Print array element
print_array(arr, size)
{
process.stdout.write("\n");
for (var i = 0; i < size; i++)
{
process.stdout.write(" " + arr[i] + " ");
}
}
//Find the maximum sum subarray of given length k
//Assuming that the length of subarray k is greater than 2
max_k_subarray(arr, size, k)
{
if (size < 2 || size < k || k < 2)
{
//When find invalid inputs
//Here can be three possibilities
//When array contains less than 2 elements, so subarray is not possible
//when array size are less than given subarray length
//Last is when given subarray have less than 2 elements
return;
}
//Set the initial resultant of sub array
var start = 0;
var last = k - 1;
var sum = 0;
var result = 0;
for (var i = 0; i < size; ++i)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//When possible of more than 1 subarray of given length k
//Remove first element of pervious subarray
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
}
//Display array elements
this.print_array(arr, size);
process.stdout.write("\nMax sum subarray of given length [" + k + "] is " + sum + ", are exist between index [" + start + "] to [" + last + "].\n");
}
}
function main()
{
var obj = new MyArray();
// Define the array elements
var arr1 = [6, 8, 1, -3, 15, 5, -4];
// Find the size
var size = arr1.length;
obj.max_k_subarray(arr1, size, 3);
// Define the array elements
var arr2 = [6, 10, -7, 2, 9, -2, 5, 1];
// Find the size
size = arr2.length;
obj.max_k_subarray(arr2, size, 4);
}
main();
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
# Python 3 Program
# Find maximum sum subarray of given size
class MyArray :
# Print array element
def print_array(self, arr, size) :
print("\n", end = "")
i = 0
while (i < size) :
print(" ", arr[i] ," ", end = "")
i += 1
# Assuming that the length of subarray k is greater than 2
# Find the maximum sum subarray of given length k
def max_k_subarray(self, arr, size, k) :
if (size < 2 or size < k or k < 2) :
# Last is when given subarray have less than 2 elements
# when array size are less than given subarray length
# When array contains less than 2 elements, so subarray is not possible
# Here can be three possibilities
# When find invalid inputs
return
# Set the initial resultant of sub array
start = 0
last = k - 1
sum = 0
result = 0
i = 0
while (i < size) :
if (k > i) :
# Get the first subarray sum
result += arr[i]
sum = result
else :
# Remove first element of pervious subarray
# When possible of more than 1 subarray of given length k
result = result - arr[i - k]
# Add current element
result = result + arr[i]
if (result > sum) :
# Modify the resultant index
start = i - (k - 1)
last = i
# Set new max sum
sum = result
i += 1
# Display array elements
self.print_array(arr, size)
print("\nMax sum subarray of given length [", k ,"] is ", sum ,", are exist between index [", start ,"] to [", last ,"].\n", end = "")
def main() :
obj = MyArray()
# Define the array elements
arr1 = [6, 8, 1, -3, 15, 5, -4]
# Find the size
size = len(arr1)
obj.max_k_subarray(arr1, size, 3)
# Define the array elements
arr2 = [6, 10, -7, 2, 9, -2, 5, 1]
# Find the size
size = len(arr2)
obj.max_k_subarray(arr2, size, 4)
if __name__ == "__main__": main()
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [ 3 ] is 17 , are exist between index [ 3 ] to [ 5 ].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [ 4 ] is 14 , are exist between index [ 1 ] to [ 4 ].
# Ruby Program
# Find maximum sum subarray of given size
class MyArray
# Print array element
def print_array(arr, size)
print("\n")
i = 0
while (i < size)
print(" ", arr[i] ," ")
i += 1
end
end
# Assuming that the length of subarray k is greater than 2
# Find the maximum sum subarray of given length k
def max_k_subarray(arr, size, k)
if (size < 2 || size < k || k < 2)
# Last is when given subarray have less than 2 elements
# when array size are less than given subarray length
# When array contains less than 2 elements, so subarray is not possible
# Here can be three possibilities
# When find invalid inputs
return
end
# Set the initial resultant of sub array
start = 0
last = k - 1
sum = 0
result = 0
i = 0
while (i < size)
if (k > i)
# Get the first subarray sum
result += arr[i]
sum = result
else
# Remove first element of pervious subarray
# When possible of more than 1 subarray of given length k
result = result - arr[i - k]
# Add current element
result = result + arr[i]
if (result > sum)
# Modify the resultant index
start = i - (k - 1)
last = i
# Set new max sum
sum = result
end
end
i += 1
end
# Display array elements
self.print_array(arr, size)
print("\nMax sum subarray of given length [", k ,"] is ", sum ,", are exist between index [", start ,"] to [", last ,"].\n")
end
end
def main()
obj = MyArray.new()
# Define the array elements
arr1 = [6, 8, 1, -3, 15, 5, -4]
# Find the size
size = arr1.length
obj.max_k_subarray(arr1, size, 3)
# Define the array elements
arr2 = [6, 10, -7, 2, 9, -2, 5, 1]
# Find the size
size = arr2.length
obj.max_k_subarray(arr2, size, 4)
end
main()
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
Scala Program
Find maximum sum subarray of given size
*/
class MyArray
{
//Print array element
def print_array(arr: Array[Int], size: Int): Unit = {
print("\n");
var i: Int = 0;
while (i < size)
{
print(" " + arr(i) + " ");
i += 1;
}
}
//Assuming that the length of subarray k is greater than 2
//Find the maximum sum subarray of given length k
def max_k_subarray(arr: Array[Int], size: Int, k: Int): Unit = {
if (size < 2 || size < k || k < 2)
{
//Last is when given subarray have less than 2 elements
//when array size are less than given subarray length
//When array contains less than 2 elements, so subarray is not possible
//Here can be three possibilities
//When find invalid inputs
return;
}
//Set the initial resultant of sub array
var start: Int = 0;
var last: Int = k - 1;
var sum: Int = 0;
var result: Int = 0;
var i: Int = 0;
while (i < size)
{
if (k > i)
{
//Get the first subarray sum
result += arr(i);
sum = result;
}
else
{
//Remove first element of pervious subarray
//When possible of more than 1 subarray of given length k
result = result - arr(i - k);
//Add current element
result = result + arr(i);
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
i += 1;
}
//Display array elements
print_array(arr, size);
print("\nMax sum subarray of given length [" + k + "] is " + sum + ", are exist between index [" + start + "] to [" + last + "].\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: MyArray = new MyArray();
// Define the array elements
var arr1: Array[Int] = Array(6, 8, 1, -3, 15, 5, -4);
// Find the size
var size: Int = arr1.length;
obj.max_k_subarray(arr1, size, 3);
// Define the array elements
var arr2: Array[Int] = Array(6, 10, -7, 2, 9, -2, 5, 1);
// Find the size
size = arr2.length;
obj.max_k_subarray(arr2, size, 4);
}
}
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [3] is 17, are exist between index [3] to [5].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [4] is 14, are exist between index [1] to [4].
/*
Swift Program
Find maximum sum subarray of given size
*/
class MyArray
{
//Print array element
func print_array(_ arr: [Int], _ size: Int)
{
print("\n", terminator: "");
var i: Int = 0;
while (i < size)
{
print(" ", arr[i] ," ", terminator: "");
i += 1;
}
}
//Assuming that the length of subarray k is greater than 2
//Find the maximum sum subarray of given length k
func max_k_subarray(_ arr: [Int], _ size: Int, _ k: Int)
{
if (size < 2 || size < k || k < 2)
{
//Last is when given subarray have less than 2 elements
//when array size are less than given subarray length
//When array contains less than 2 elements, so subarray is not possible
//Here can be three possibilities
//When find invalid inputs
return;
}
//Set the initial resultant of sub array
var start: Int = 0;
var last: Int = k - 1;
var sum: Int = 0;
var result: Int = 0;
var i: Int = 0;
while (i < size)
{
if (k > i)
{
//Get the first subarray sum
result += arr[i];
sum = result;
}
else
{
//Remove first element of pervious subarray
//When possible of more than 1 subarray of given length k
result = result - arr[i - k];
//Add current element
result = result + arr[i];
if (result > sum)
{
//Modify the resultant index
start = i - (k - 1);
last = i;
//Set new max sum
sum = result;
}
}
i += 1;
}
//Display array elements
self.print_array(arr, size);
print("\nMax sum subarray of given length [", k ,"] is ", sum ,", are exist between index [", start ,"] to [", last ,"].\n", terminator: "");
}
}
func main()
{
let obj: MyArray = MyArray();
// Define the array elements
let arr1: [Int] = [6, 8, 1, -3, 15, 5, -4];
// Find the size
var size: Int = arr1.count;
obj.max_k_subarray(arr1, size, 3);
// Define the array elements
let arr2: [Int] = [6, 10, -7, 2, 9, -2, 5, 1];
// Find the size
size = arr2.count;
obj.max_k_subarray(arr2, size, 4);
}
main();
Output
6 8 1 -3 15 5 -4
Max sum subarray of given length [ 3 ] is 17 , are exist between index [ 3 ] to [ 5 ].
6 10 -7 2 9 -2 5 1
Max sum subarray of given length [ 4 ] is 14 , are exist between index [ 1 ] to [ 4 ].
Time Complexity
The time complexity of finding the maximum sum subarray of a given size 'k' using the provided algorithm is O(n), where 'n' is the number of elements in the array. This is because the algorithm iterates through the array only once, updating the sum and the result at each step.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment