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:

1. Initialize variables to track the current subarray's start index, end index, and result (maximum sum).
2. Iterate through the array and calculate the current sum.
3. If the current sum is greater than the result, update the result and the subarray indices.
4. If the current sum becomes negative, reset the subarray start index and current sum.
5. 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

1. The sizeMaxSumSubarray function iterates through the array and keeps track of the subarray start and end indices, the current sum, and the maximum result.
2. When the current sum is greater than the result, the function updates the subarray indices and result.
3. When the current sum becomes negative, the function resets the temporary index and current sum.
4. The size of the maximum sum subarray is calculated as (end index - start index + 1).

• C
• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

// 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;
}

  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);
    }
}

 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;
}

 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);
	}
}

 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)
}

 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();

 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();

 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()

  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()

 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);
	}
}

 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();

  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);
}

 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.