Find the size of maximum sum subarray
The problem we are addressing here is to find the size of the maximum sum subarray within a given array. This involves finding a contiguous subarray within the array such that the sum of its elements is maximized, and then determining the size of that subarray.
For instance, given an array [1, 2, -5, 1, 2, -3, 3, -2, 8, -4]
, we need to find the maximum sum
subarray and its size.
Problem Statement
The problem requires identifying the size of the subarray with the maximum sum among all possible subarrays in the given array.
Explanation with Example
Let's consider the example provided: arr = [1, 2, -5, 1, 2, -3, 3, -2, 8, -4]
.
We need to find the subarray with the maximum sum:
- Subarray:
[1, 2, -3, 3, -2, 8]
- Sum:
1 + 2 + -3 + 3 + -2 + 8 = 9
So, the size of the maximum sum subarray is 6.
Idea to Solve the Problem
To solve this problem, we can break down the process into several steps:
- Initialize variables to track the current subarray's start index, end index, and result (maximum sum).
- Iterate through the array and calculate the current sum.
- If the current sum is greater than the result, update the result and the subarray indices.
- If the current sum becomes negative, reset the subarray start index and current sum.
- The size of the maximum sum subarray is
(end index - start index + 1)
.
Pseudocode
Function sizeMaxSumSubarray(arr, n):
s = 0 (subarray start index)
e = 0 (subarray end index)
temp = 0 (temporary index)
result = INT_MIN (maximum sum)
sum = 0 (current sum)
for i from 0 to n - 1:
sum = sum + arr[i]
if result < sum:
s = temp
e = i
result = sum
if sum < 0:
temp = i + 1
sum = 0
result = e - s + 1
printArray(arr, n)
print "Result:", result
Algorithm Explanation
- The
sizeMaxSumSubarray
function iterates through the array and keeps track of the subarray start and end indices, the current sum, and the maximum result. - When the current sum is greater than the result, the function updates the subarray indices and result.
- When the current sum becomes negative, the function resets the temporary index and current sum.
- The size of the maximum sum subarray is calculated as
(end index - start index + 1)
.
// C Program
// Find the size of maximum sum subarray
#include <stdio.h>
#include <limits.h>
void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
printf(" %d", arr[i]);
}
printf("\n");
}
void sizeMaxSumSubarray(int arr[], int n)
{
// Resultant index
int s = 0, e = 0;
// Auxiliary variables
int temp = 0;
int result = INT_MIN;
int sum = 0;
for (int i = 0; i < n; ++i)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
}
result = (e - s + 1);
printArray(arr, n);
printf(" Result : %d \n", result);
}
int main()
{
// Given array elements
int arr1[] = {
1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8 , -4
};
int arr2[] = {
-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
};
// Test A
// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1[0]);
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);
// [3, 1, 2, 8]
// Result 4
sizeMaxSumSubarray(arr2, n);
return 0;
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Java program for
// Find the size of maximum sum subarray
public class SubArray
{
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
System.out.print(" " + arr[i] );
}
System.out.print("\n");
}
public void sizeMaxSumSubarray(int[] arr, int n)
{
// Resultant index
int s = 0, e = 0;
// Auxiliary variables
int temp = 0;
int result = Integer.MIN_VALUE;
int sum = 0;
for (int i = 0; i < n; ++i)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
}
result = (e - s + 1);
printArray(arr, n);
System.out.print(" Result : " + result + " \n");
}
public static void main(String[] args)
{
SubArray task = new SubArray();
// Given array elements
int[] arr1 = {
1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8 , -4
};
int[] arr2 = {
-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
};
// Test A
// Get the number of elements
int n = arr1.length;
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.length;
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Include header file
#include <iostream>
#include <limits.h>
using namespace std;
// C++ program for
// Find the size of maximum sum subarray
class SubArray
{
public: void printArray(int arr[], int n)
{
for (int i = 0; i < n; ++i)
{
cout << " " << arr[i];
}
cout << "\n";
}
void sizeMaxSumSubarray(int arr[], int n)
{
// Resultant index
int s = 0;
int e = 0;
// Auxiliary variables
int temp = 0;
int result = INT_MIN;
int sum = 0;
for (int i = 0; i < n; ++i)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
}
result = (e - s + 1);
this->printArray(arr, n);
cout << " Result : " << result << " \n";
}
};
int main()
{
SubArray *task = new SubArray();
// Given array elements
int arr1[] = {
1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8 , -4
};
int arr2[] = {
-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
};
// Test A
// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1[0]);
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task->sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);
// [3, 1, 2, 8]
// Result 4
task->sizeMaxSumSubarray(arr2, n);
return 0;
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Include namespace system
using System;
// Csharp program for
// Find the size of maximum sum subarray
public class SubArray
{
public void printArray(int[] arr, int n)
{
for (int i = 0; i < n; ++i)
{
Console.Write(" " + arr[i]);
}
Console.Write("\n");
}
public void sizeMaxSumSubarray(int[] arr, int n)
{
// Resultant index
int s = 0;
int e = 0;
// Auxiliary variables
int temp = 0;
int result = int.MinValue;
int sum = 0;
for (int i = 0; i < n; ++i)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
}
result = (e - s + 1);
this.printArray(arr, n);
Console.Write(" Result : " + result + " \n");
}
public static void Main(String[] args)
{
SubArray task = new SubArray();
// Given array elements
int[] arr1 = {
1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8 , -4
};
int[] arr2 = {
-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
};
// Test A
// Get the number of elements
int n = arr1.Length;
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.Length;
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
package main
import "math"
import "fmt"
// Go program for
// Find the size of maximum sum subarray
func printArray(arr[] int, n int) {
for i := 0 ; i < n ; i++ {
fmt.Print(" ", arr[i])
}
fmt.Print("\n")
}
func sizeMaxSumSubarray(arr[] int, n int) {
// Resultant index
var s int = 0
var e int = 0
// Auxiliary variables
var temp int = 0
var result int = math.MinInt64
var sum int = 0
for i := 0 ; i < n ; i++ {
// Current sum
sum += arr[i]
if result < sum {
// When sum is greater than result.
// Get resultant intex.
s = temp
e = i
// Change sum
result = sum
}
if sum < 0 {
temp = i + 1
// Reset sum
sum = 0
}
}
result = (e - s + 1)
printArray(arr, n)
fmt.Print(" Result : ", result, " \n")
}
func main() {
// Given array elements
var arr1 = [] int {1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8, -4}
var arr2 = [] int {-5, 1, 2, -10, 3, 1, 2, 8, -2}
// Test A
// Get the number of elements
var n int = len(arr1)
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
sizeMaxSumSubarray(arr1, n)
// Test B
// Get the number of elements
n = len(arr2)
// [3, 1, 2, 8]
// Result 4
sizeMaxSumSubarray(arr2, n)
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
<?php
// Php program for
// Find the size of maximum sum subarray
class SubArray
{
public function printArray($arr, $n)
{
for ($i = 0; $i < $n; ++$i)
{
echo(" ".$arr[$i]);
}
echo("\n");
}
public function sizeMaxSumSubarray($arr, $n)
{
// Resultant index
$s = 0;
$e = 0;
// Auxiliary variables
$temp = 0;
$result = -PHP_INT_MAX;
$sum = 0;
for ($i = 0; $i < $n; ++$i)
{
// Current sum
$sum += $arr[$i];
if ($result < $sum)
{
// When sum is greater than result.
// Get resultant intex.
$s = $temp;
$e = $i;
// Change sum
$result = $sum;
}
if ($sum < 0)
{
$temp = $i + 1;
// Reset sum
$sum = 0;
}
}
$result = ($e - $s + 1);
$this->printArray($arr, $n);
echo(" Result : ".$result." \n");
}
}
function main()
{
$task = new SubArray();
// Given array elements
$arr1 = array(1, 2, -5, 1, 2, -3, 3, -2, 8, -4);
$arr2 = array(-5, 1, 2, -10, 3, 1, 2, 8, -2);
// Test A
// Get the number of elements
$n = count($arr1);
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
$task->sizeMaxSumSubarray($arr1, $n);
// Test B
// Get the number of elements
$n = count($arr2);
// [3, 1, 2, 8]
// Result 4
$task->sizeMaxSumSubarray($arr2, $n);
}
main();
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Node JS program for
// Find the size of maximum sum subarray
class SubArray
{
printArray(arr, n)
{
for (var i = 0; i < n; ++i)
{
process.stdout.write(" " + arr[i]);
}
process.stdout.write("\n");
}
sizeMaxSumSubarray(arr, n)
{
// Resultant index
var s = 0;
var e = 0;
// Auxiliary variables
var temp = 0;
var result = -Number.MAX_VALUE;
var sum = 0;
for (var i = 0; i < n; ++i)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
}
result = (e - s + 1);
this.printArray(arr, n);
process.stdout.write(" Result : " + result + " \n");
}
}
function main()
{
var task = new SubArray();
// Given array elements
var arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8, -4];
var arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2];
// Test A
// Get the number of elements
var n = arr1.length;
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.length;
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
main();
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
import sys
# Python 3 program for
# Find the size of maximum sum subarray
class SubArray :
def printArray(self, arr, n) :
i = 0
while (i < n) :
print(" ", arr[i], end = "")
i += 1
print(end = "\n")
def sizeMaxSumSubarray(self, arr, n) :
# Resultant index
s = 0
e = 0
# Auxiliary variables
temp = 0
result = -sys.maxsize
sum = 0
i = 0
while (i < n) :
# Current sum
sum += arr[i]
if (result < sum) :
# When sum is greater than result.
# Get resultant intex.
s = temp
e = i
# Change sum
result = sum
if (sum < 0) :
temp = i + 1
# Reset sum
sum = 0
i += 1
result = (e - s + 1)
self.printArray(arr, n)
print(" Result : ", result ," ")
def main() :
task = SubArray()
# Given list elements
arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8, -4]
arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2]
# Test A
# Get the number of elements
n = len(arr1)
# [1 , 2 , -3 , 3 , -2 , 8]
# Result : 6
task.sizeMaxSumSubarray(arr1, n)
# Test B
# Get the number of elements
n = len(arr2)
# [3, 1, 2, 8]
# Result 4
task.sizeMaxSumSubarray(arr2, n)
if __name__ == "__main__": main()
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
# Ruby program for
# Find the size of maximum sum subarray
class SubArray
def printArray(arr, n)
i = 0
while (i < n)
print(" ", arr[i])
i += 1
end
print("\n")
end
def sizeMaxSumSubarray(arr, n)
# Resultant index
s = 0
e = 0
# Auxiliary variables
temp = 0
result = -(2 ** (0. size * 8 - 2))
sum = 0
i = 0
while (i < n)
# Current sum
sum += arr[i]
if (result < sum)
# When sum is greater than result.
# Get resultant intex.
s = temp
e = i
# Change sum
result = sum
end
if (sum < 0)
temp = i + 1
# Reset sum
sum = 0
end
i += 1
end
result = (e - s + 1)
self.printArray(arr, n)
print(" Result : ", result ," \n")
end
end
def main()
task = SubArray.new()
# Given array elements
arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8, -4]
arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2]
# Test A
# Get the number of elements
n = arr1.length
# [1 , 2 , -3 , 3 , -2 , 8]
# Result : 6
task.sizeMaxSumSubarray(arr1, n)
# Test B
# Get the number of elements
n = arr2.length
# [3, 1, 2, 8]
# Result 4
task.sizeMaxSumSubarray(arr2, n)
end
main()
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Scala program for
// Find the size of maximum sum subarray
class SubArray()
{
def printArray(arr: Array[Int], n: Int): Unit = {
var i: Int = 0;
while (i < n)
{
print(" " + arr(i));
i += 1;
}
print("\n");
}
def sizeMaxSumSubarray(arr: Array[Int], n: Int): Unit = {
// Resultant index
var s: Int = 0;
var e: Int = 0;
// Auxiliary variables
var temp: Int = 0;
var result: Int = Int.MinValue;
var sum: Int = 0;
var i: Int = 0;
while (i < n)
{
// Current sum
sum += arr(i);
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
i += 1;
}
result = (e - s + 1);
printArray(arr, n);
print(" Result : " + result + " \n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubArray = new SubArray();
// Given array elements
var arr1: Array[Int] = Array(1, 2, -5, 1, 2, -3, 3, -2, 8, -4);
var arr2: Array[Int] = Array(-5, 1, 2, -10, 3, 1, 2, 8, -2);
// Test A
// Get the number of elements
var n: Int = arr1.length;
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.length;
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
import Foundation;
// Swift 4 program for
// Find the size of maximum sum subarray
class SubArray
{
func printArray(_ arr: [Int], _ n: Int)
{
var i: Int = 0;
while (i < n)
{
print(" ", arr[i], terminator: "");
i += 1;
}
print(terminator: "\n");
}
func sizeMaxSumSubarray(_ arr: [Int], _ n: Int)
{
// Resultant index
var s: Int = 0;
var e: Int = 0;
// Auxiliary variables
var temp: Int = 0;
var result: Int = Int.min;
var sum: Int = 0;
var i: Int = 0;
while (i < n)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
i += 1;
}
result = (e - s + 1);
self.printArray(arr, n);
print(" Result : ", result ," ");
}
}
func main()
{
let task: SubArray = SubArray();
// Given array elements
let arr1: [Int] = [1, 2, -5, 1, 2, -3, 3, -2, 8, -4];
let arr2: [Int] = [-5, 1, 2, -10, 3, 1, 2, 8, -2];
// Test A
// Get the number of elements
var n: Int = arr1.count;
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.count;
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
main();
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
// Kotlin program for
// Find the size of maximum sum subarray
class SubArray
{
fun printArray(arr: Array < Int > , n: Int): Unit
{
var i: Int = 0;
while (i < n)
{
print(" " + arr[i]);
i += 1;
}
print("\n");
}
fun sizeMaxSumSubarray(arr: Array < Int > , n: Int): Unit
{
// Resultant index
var s: Int = 0;
var e: Int = 0;
// Auxiliary variables
var temp: Int = 0;
var result: Int = Int.MIN_VALUE;
var sum: Int = 0;
var i: Int = 0;
while (i < n)
{
// Current sum
sum += arr[i];
if (result < sum)
{
// When sum is greater than result.
// Get resultant intex.
s = temp;
e = i;
// Change sum
result = sum;
}
if (sum < 0)
{
temp = i + 1;
// Reset sum
sum = 0;
}
i += 1;
}
result = (e - s + 1);
this.printArray(arr, n);
print(" Result : " + result + " \n");
}
}
fun main(args: Array < String > ): Unit
{
val task: SubArray = SubArray();
// Given array elements
val arr1: Array < Int > = arrayOf(1, 2, -5, 1, 2, -3, 3, -2, 8, -4);
val arr2: Array < Int > = arrayOf(-5, 1, 2, -10, 3, 1, 2, 8, -2);
// Test A
// Get the number of elements
var n: Int = arr1.count();
// [1 , 2 , -3 , 3 , -2 , 8]
// Result : 6
task.sizeMaxSumSubarray(arr1, n);
// Test B
// Get the number of elements
n = arr2.count();
// [3, 1, 2, 8]
// Result 4
task.sizeMaxSumSubarray(arr2, n);
}
Output
1 2 -5 1 2 -3 3 -2 8 -4
Result : 6
-5 1 2 -10 3 1 2 8 -2
Result : 4
Time Complexity Analysis
- The
sizeMaxSumSubarray
function iterates through the array once, so it has a linear time complexity of O(n), where n is the number of elements in the array.
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