Skip to main content

Find the size of maximum sum subarray

Here given code implementation process.

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




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