Skip to main content

Largest sum contiguous subarray

Here given code implementation process.

// C program for 
// Largest sum contiguous subarray
#include <stdio.h>

// This is display the element of given array
void printElement(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		// Array element
		printf("  %d", arr[i]);
	}
	printf("\n");
}
void maxContiguous(int arr[], int n)
{
	if (n <= 0)
	{
		return;
	}
	// Define some useful resultant auxiliary variables
	// Get first element
	int result = arr[0];
	int auxiliary = result;
	// Executes the loop through by size of array
	for (int i = 1; i < n; i++)
	{
		// Add new element into auxiliary variable
		auxiliary = auxiliary + arr[i];
		if (result < auxiliary)
		{
			// When auxiliary contain new result
			result = auxiliary;
		}
		if (auxiliary < 0)
		{
			// When auxiliary are less than zero
			auxiliary = 0;
		}
	}
	// Display array elements
	printElement(arr, n);
	// Display calculated result
	printf(" Result : %d\n", result);
}
int main(int argc, char const *argv[])
{
	// Array of integer elements
	int arr1[] = {
		1 , 4 , -6 , 6 , 1 , -3 , 4 , -1 , 2 , -4 , -4 , 6
	};
	int arr2[] = {
		1 , 2 , 3 , -7 , 1 , 2 , -4 , 3 , 5 , -2
	};
	// Test A
	// Get the number of elements
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// [ 6, 1, -3 , 4, -1, 2] 
	maxContiguous(arr1, n);
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3,5]
	maxContiguous(arr2, n);
	return 0;
}

input

  1  4  -6  6  1  -3  4  -1  2  -4  -4  6
 Result : 9
  1  2  3  -7  1  2  -4  3  5  -2
 Result : 8
/*
  Java Program for 
  Largest sum contiguous subarray
*/
public class Subarray
{
	// This is display the element of given array
	public void printElement(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			// Array element
			System.out.print(" " + arr[i]);
		}
		System.out.print("\n");
	}
	public void maxContiguous(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		int result = arr[0];
		int auxiliary = result;
		// Executes the loop through by size of array
		for (int i = 1; i < n; i++)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
		}
		// Display array elements
		printElement(arr, n);
		// Display calculated result
		System.out.println(" Result : " + result);
	}
	public static void main(String[] args)
	{
		Subarray task = new Subarray();
		// Array of integer elements
		int[] arr1 = {
			1 , 4 , -6 , 6 , 1 , -3 , 4 , -1 , 2 , -4 , -4 , 6
		};
		int[] arr2 = {
			1 , 2 , 3 , -7 , 1 , 2 , -4 , 3 , 5 , -2
		};
		// Test A
		// Get the number of elements
		int n = arr1.length;
		// [ 6, 1, -3 , 4, -1, 2] 
		task.maxContiguous(arr1, n);
		// Test B
		n = arr2.length;
		// [3,5]
		task.maxContiguous(arr2, n);
	}
}

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
// Include header file
#include <iostream>

using namespace std;
/*
  C++ Program for 
  Largest sum contiguous subarray
*/
class Subarray
{
	public:
		// This is display the element of given array
		void printElement(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				// Array element
				cout << " " << arr[i];
			}
			cout << endl;
		}
	void maxContiguous(int arr[], int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		int result = arr[0];
		int auxiliary = result;
		// Executes the loop through by size of array
		for (int i = 1; i < n; i++)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
		}
		// Display array elements
		this->printElement(arr, n);
		// Display calculated result
		cout << " Result : " << result << endl;
	}
};
int main()
{
	Subarray *task = new Subarray();
	// Array of integer elements
	int arr1[] = {
		1 , 4 , -6 , 6 , 1 , -3 , 4 , -1 , 2 , -4 , -4 , 6
	};
	int arr2[] = {
		1 , 2 , 3 , -7 , 1 , 2 , -4 , 3 , 5 , -2
	};
	// Test A
	// Get the number of elements
	int n = sizeof(arr1) / sizeof(arr1[0]);
	// [ 6, 1, -3 , 4, -1, 2] 
	task->maxContiguous(arr1, n);
	// Test B
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3,5]
	task->maxContiguous(arr2, n);
	return 0;
}

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
// Include namespace system
using System;
/*
  Csharp Program for 
  Largest sum contiguous subarray
*/
public class Subarray
{
	// This is display the element of given array
	public void printElement(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			// Array element
			Console.Write(" " + arr[i]);
		}
		Console.Write("\n");
	}
	public void maxContiguous(int[] arr, int n)
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		int result = arr[0];
		int auxiliary = result;
		// Executes the loop through by size of array
		for (int i = 1; i < n; i++)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
		}
		// Display array elements
		this.printElement(arr, n);
		// Display calculated result
		Console.WriteLine(" Result : " + result);
	}
	public static void Main(String[] args)
	{
		Subarray task = new Subarray();
		// Array of integer elements
		int[] arr1 = {
			1 , 4 , -6 , 6 , 1 , -3 , 4 , -1 , 2 , -4 , -4 , 6
		};
		int[] arr2 = {
			1 , 2 , 3 , -7 , 1 , 2 , -4 , 3 , 5 , -2
		};
		// Test A
		// Get the number of elements
		int n = arr1.Length;
		// [ 6, 1, -3 , 4, -1, 2] 
		task.maxContiguous(arr1, n);
		// Test B
		n = arr2.Length;
		// [3,5]
		task.maxContiguous(arr2, n);
	}
}

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
<?php
/*
  Php Program for 
  Largest sum contiguous subarray
*/
class Subarray
{
	// This is display the element of given array
	public	function printElement($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			// Array element
			echo " ".$arr[$i];
		}
		echo "\n";
	}
	public	function maxContiguous($arr, $n)
	{
		if ($n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		$result = $arr[0];
		$auxiliary = $result;
		// Executes the loop through by size of array
		for ($i = 1; $i < $n; $i++)
		{
			// Add new element into auxiliary variable
			$auxiliary = $auxiliary + $arr[$i];
			if ($result < $auxiliary)
			{
				// When auxiliary contain new result
				$result = $auxiliary;
			}
			if ($auxiliary < 0)
			{
				// When auxiliary are less than zero
				$auxiliary = 0;
			}
		}
		// Display array elements
		$this->printElement($arr, $n);
		// Display calculated result
		echo " Result : ".$result.
		"\n";
	}
}

function main()
{
	$task = new Subarray();
	// Array of integer elements
	$arr1 = array(1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6);
	$arr2 = array(1, 2, 3, -7, 1, 2, -4, 3, 5, -2);
	// Test A
	// Get the number of elements
	$n = count($arr1);
	// [ 6, 1, -3 , 4, -1, 2] 
	$task->maxContiguous($arr1, $n);
	// Test B
	$n = count($arr2);
	// [3,5]
	$task->maxContiguous($arr2, $n);
}
main();

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
/*
  Node JS Program for 
  Largest sum contiguous subarray
*/
class Subarray
{
	// This is display the element of given array
	printElement(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			// Array element
			process.stdout.write(" " + arr[i]);
		}
		process.stdout.write("\n");
	}
	maxContiguous(arr, n)
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		var result = arr[0];
		var auxiliary = result;
		// Executes the loop through by size of array
		for (var i = 1; i < n; i++)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
		}
		// Display array elements
		this.printElement(arr, n);
		// Display calculated result
		console.log(" Result : " + result);
	}
}

function main()
{
	var task = new Subarray();
	// Array of integer elements
	var arr1 = [1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6];
	var arr2 = [1, 2, 3, -7, 1, 2, -4, 3, 5, -2];
	// Test A
	// Get the number of elements
	var n = arr1.length;
	// [ 6, 1, -3 , 4, -1, 2] 
	task.maxContiguous(arr1, n);
	// Test B
	n = arr2.length;
	// [3,5]
	task.maxContiguous(arr2, n);
}
main();

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
#  Python 3 Program for 
#  Largest sum contiguous subarray
class Subarray :
	#  This is display the element of given list
	def printElement(self, arr, n) :
		i = 0
		while (i < n) :
			#  Array element
			print(" ", arr[i], end = "")
			i += 1
		
		print(end = "\n")
	
	def maxContiguous(self, arr, n) :
		if (n <= 0) :
			return
		
		result = arr[0]
		auxiliary = result
		#  Executes the loop through by size of list
		i = 1
		while (i < n) :
			#  Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i]
			if (result < auxiliary) :
				#  When auxiliary contain new result
				result = auxiliary
			
			if (auxiliary < 0) :
				#  When auxiliary are less than zero
				auxiliary = 0
			
			i += 1
		
		#  Display list elements
		self.printElement(arr, n)
		#  Display calculated result
		print(" Result : ", result)
	

def main() :
	task = Subarray()
	arr1 = [1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6]
	arr2 = [1, 2, 3, -7, 1, 2, -4, 3, 5, -2]
	n = len(arr1)
	#  [ 6, 1, -3 , 4, -1, 2] 
	task.maxContiguous(arr1, n)
	#  Test B
	n = len(arr2)
	#  [3,5]
	task.maxContiguous(arr2, n)

if __name__ == "__main__": main()

input

  1  4  -6  6  1  -3  4  -1  2  -4  -4  6
 Result :  9
  1  2  3  -7  1  2  -4  3  5  -2
 Result :  8
#  Ruby Program for 
#  Largest sum contiguous subarray
class Subarray 
	#  This is display the element of given array
	def printElement(arr, n) 
		i = 0
		while (i < n) 
			#  Array element
			print(" ", arr[i])
			i += 1
		end

		print("\n")
	end

	def maxContiguous(arr, n) 
		if (n <= 0) 
			return
		end

		#  Define some useful resultant auxiliary variables
		#  Get first element
		result = arr[0]
		auxiliary = result
		#  Executes the loop through by size of array
		i = 1
		while (i < n) 
			#  Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i]
			if (result < auxiliary) 
				#  When auxiliary contain new result
				result = auxiliary
			end

			if (auxiliary < 0) 
				#  When auxiliary are less than zero
				auxiliary = 0
			end

			i += 1
		end

		#  Display array elements
		self.printElement(arr, n)
		#  Display calculated result
		print(" Result : ", result, "\n")
	end

end

def main() 
	task = Subarray.new()
	#  Array of integer elements
	arr1 = [1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6]
	arr2 = [1, 2, 3, -7, 1, 2, -4, 3, 5, -2]
	#  Test A
	#  Get the number of elements
	n = arr1.length
	#  [ 6, 1, -3 , 4, -1, 2] 
	task.maxContiguous(arr1, n)
	#  Test B
	n = arr2.length
	#  [3,5]
	task.maxContiguous(arr2, n)
end

main()

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
/*
  Scala Program for 
  Largest sum contiguous subarray
*/
class Subarray()
{
	// This is display the element of given array
	def printElement(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			// Array element
			print(" " + arr(i));
			i += 1;
		}
		print("\n");
	}
	def maxContiguous(arr: Array[Int], n: Int): Unit = {
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		var result: Int = arr(0);
		var auxiliary: Int = result;
		// Executes the loop through by size of array
		var i: Int = 1;
		while (i < n)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr(i);
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
			i += 1;
		}
		// Display array elements
		printElement(arr, n);
		// Display calculated result
		println(" Result : " + result);
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: Subarray = new Subarray();
		// Array of integer elements
		var arr1: Array[Int] = Array(1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6);
		var arr2: Array[Int] = Array(1, 2, 3, -7, 1, 2, -4, 3, 5, -2);
		// Test A
		// Get the number of elements
		var n: Int = arr1.length;
		// [ 6, 1, -3 , 4, -1, 2] 
		task.maxContiguous(arr1, n);
		// Test B
		n = arr2.length;
		// [3,5]
		task.maxContiguous(arr2, n);
	}
}

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8
/*
  Swift 4 Program for 
  Largest sum contiguous subarray
*/
class Subarray
{
	// This is display the element of given array
	func printElement(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			// Array element
			print(" ", arr[i], terminator: "");
			i += 1;
		}
		print(terminator: "\n");
	}
	func maxContiguous(_ arr: [Int], _ n: Int)
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		var result: Int = arr[0];
		var auxiliary: Int = result;
		// Executes the loop through by size of array
		var i: Int = 1;
		while (i < n)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
			i += 1;
		}
		// Display array elements
		self.printElement(arr, n);
		// Display calculated result
		print(" Result : ", result);
	}
}
func main()
{
	let task: Subarray = Subarray();
	// Array of integer elements
	let arr1: [Int] = [1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6];
	let arr2: [Int] = [1, 2, 3, -7, 1, 2, -4, 3, 5, -2];
	// Test A
	// Get the number of elements
	var n: Int = arr1.count;
	// [ 6, 1, -3 , 4, -1, 2] 
	task.maxContiguous(arr1, n);
	// Test B
	n = arr2.count;
	// [3,5]
	task.maxContiguous(arr2, n);
}
main();

input

  1  4  -6  6  1  -3  4  -1  2  -4  -4  6
 Result :  9
  1  2  3  -7  1  2  -4  3  5  -2
 Result :  8
/*
  Kotlin Program for 
  Largest sum contiguous subarray
*/
class Subarray
{
	// This is display the element of given array
	fun printElement(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			// Array element
			print(" " + arr[i]);
			i += 1;
		}
		print("\n");
	}
	fun maxContiguous(arr: Array < Int > , n: Int): Unit
	{
		if (n <= 0)
		{
			return;
		}
		// Define some useful resultant auxiliary variables
		// Get first element
		var result: Int = arr[0];
		var auxiliary: Int = result;
		var i: Int = 1;
		while (i < n)
		{
			// Add new element into auxiliary variable
			auxiliary = auxiliary + arr[i];
			if (result < auxiliary)
			{
				// When auxiliary contain new result
				result = auxiliary;
			}
			if (auxiliary < 0)
			{
				// When auxiliary are less than zero
				auxiliary = 0;
			}
			i += 1;
		}
		// Display array elements
		this.printElement(arr, n);
		// Display calculated result
		println(" Result : " + result);
	}
}
fun main(args: Array < String > ): Unit
{
	val task: Subarray = Subarray();
	// Array of integer elements
	val arr1: Array < Int > = arrayOf(1, 4, -6, 6, 1, -3, 4, -1, 2, -4, -4, 6);
	val arr2: Array < Int > = arrayOf(1, 2, 3, -7, 1, 2, -4, 3, 5, -2);
	// Test A
	// Get the number of elements
	var n: Int = arr1.count();
	// [ 6, 1, -3 , 4, -1, 2] 
	task.maxContiguous(arr1, n);
	// Test B
	n = arr2.count();
	// [3,5]
	task.maxContiguous(arr2, n);
}

input

 1 4 -6 6 1 -3 4 -1 2 -4 -4 6
 Result : 9
 1 2 3 -7 1 2 -4 3 5 -2
 Result : 8




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