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