Skip to main content

Find maximum sum subarray of given size

Here given code implementation process.

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