Posted on by Kalkicode
Code Array

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

1. Array: `[6, 8, 1, -3, 15, 5, -4]`, k = 3

• The maximum sum subarray of size 3 is `[15, 5, -4]`, and the sum is `15 + 5 + (-4) = 16`.
2. 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 is `10 + (-7) + 2 + 9 = 14`.

## Idea to Solve the Problem

To solve this problem, we can use a sliding window approach. Here are the steps:

1. Initialize two pointers, `start` and `last`, both set to `0`, and a variable `sum` to store the sum of the current subarray.
2. 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 the `sum` and add the current element to the `sum`.
• If the current `sum` is greater than the previous maximum sum, update the `start` and `last` pointers and the `sum`.
3. 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

1. Initialize `start` and `last` to 0, `sum` to 0, and `result` to 0.
2. Iterate through the array using a loop from `0` to `size - 1`.
3. If `i` is less than `k`, add the element at `arr[i]` to the `sum` and update `result`.
4. Otherwise, remove the element at `arr[i - k]` from the `sum` and add the element at `arr[i]` to the `sum`.
5. If the current `sum` is greater than `result`, update `start`, `last`, and `result`.
6. 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];
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];
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];
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];
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];
\$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];
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);
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];
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.

## Comment

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.

Categories
Relative Post