Skip to main content

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];
			//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.

Last updated on by Kalkicode




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.

New Comment