Skip to main content

kadane's algorithm for maximum sum subarray

Kadane's algorithm is a popular algorithm used to find the maximum sum subarray of a given array of integers. The subarray is a contiguous subset of the original array.

The algorithm works by iterating through the array and keeping track of two variables: the maximum sum seen so far, and the maximum sum ending at the current index. At each index, the algorithm compares the maximum sum ending at the current index plus the current element to the current element itself. If the former is greater, the maximum sum ending at the current index is updated; otherwise, the maximum sum ending at the current index starts anew with the current element.

The maximum sum seen so far is updated whenever the maximum sum ending at the current index is greater than the maximum sum seen so far.

Here given code implementation process.

// C Program
// kadane's algorithm for maximum sum subarray
#include <stdio.h>

// Returns a maximum value of given number
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
int findMaxSumSubarray(int arr[], int n)
{
	int bestSum = 0;
	int currentSum = 0;
	for (int i = 0; i < n; ++i)
	{
		// Sum of subarray
		currentSum = maxValue(0, currentSum + arr[i]);
		// Get best result
		bestSum = maxValue(bestSum, currentSum);
	}
	return bestSum;
}
int main()
{
	// Given array elements
	int arr1[] = {
		1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8
	};
	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]);
	// [3, -2,  8]
	// Result 9
	int result = findMaxSumSubarray(arr1, n);
	printf("\n %d", result);
	// Test B
	// Get the number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3, 1, 2, 8]
	// Result 14
	result = findMaxSumSubarray(arr2, n);
	printf("\n %d", result);
	return 0;
}

Output

 9
 14
/*
    Java Program
    kadane's algorithm for maximum sum subarray
*/
public class MaxSubArray
{
	// Returns a maximum value of given number
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int findMaxSumSubarray(int[] arr, int n)
	{
		int bestSum = 0;
		int currentSum = 0;
		for (int i = 0; i < n; ++i)
		{
			// Sum of subarray
			currentSum = maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = maxValue(bestSum, currentSum);
		}
		return bestSum;
	}
	public static void main(String[] args)
	{
		MaxSubArray task = new MaxSubArray();
		// Given array elements
		int[] arr1 = {
			1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8
		};
		int[] arr2 = {
			-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
		};
		// Test A
		// Get the number of elements
		int n = arr1.length;
		// [3, -2,  8]
		// Result 9
		int result = task.findMaxSumSubarray(arr1, n);
		System.out.print("\n " + result);
		// Test B
		// Get the number of elements
		n = arr2.length;
		// [3, 1, 2, 8]
		// Result 14
		result = task.findMaxSumSubarray(arr2, n);
		System.out.print("\n " + result);
	}
}

Output

 9
 14
// Include header file
#include <iostream>
using namespace std;
/*
    C++ Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray
{
	public:
		// Returns a maximum value of given number
		int maxValue(int a, int b)
		{
			if (a > b)
			{
				return a;
			}
			return b;
		}
	int findMaxSumSubarray(int arr[], int n)
	{
		int bestSum = 0;
		int currentSum = 0;
		for (int i = 0; i < n; ++i)
		{
			// Sum of subarray
			currentSum = this->maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = this->maxValue(bestSum, currentSum);
		}
		return bestSum;
	}
};
int main()
{
	MaxSubArray *task = new MaxSubArray();
	// Given array elements
	int arr1[] = {
		1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8
	};
	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]);
	// [3, -2,  8]
	// Result 9
	int result = task->findMaxSumSubarray(arr1, n);
	cout << "\n " << result;
	// Test B
	// Get the number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3, 1, 2, 8]
	// Result 14
	result = task->findMaxSumSubarray(arr2, n);
	cout << "\n " << result;
	return 0;
}

Output

 9
 14
// Include namespace system
using System;
/*
    Csharp Program
    kadane's algorithm for maximum sum subarray
*/
public class MaxSubArray
{
	// Returns a maximum value of given number
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int findMaxSumSubarray(int[] arr, int n)
	{
		int bestSum = 0;
		int currentSum = 0;
		for (int i = 0; i < n; ++i)
		{
			// Sum of subarray
			currentSum = this.maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = this.maxValue(bestSum, currentSum);
		}
		return bestSum;
	}
	public static void Main(String[] args)
	{
		MaxSubArray task = new MaxSubArray();
		// Given array elements
		int[] arr1 = {
			1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8
		};
		int[] arr2 = {
			-5 , 1 , 2 , -10 , 3 , 1 , 2 , 8 , -2
		};
		// Test A
		// Get the number of elements
		int n = arr1.Length;
		// [3, -2,  8]
		// Result 9
		int result = task.findMaxSumSubarray(arr1, n);
		Console.Write("\n " + result);
		// Test B
		// Get the number of elements
		n = arr2.Length;
		// [3, 1, 2, 8]
		// Result 14
		result = task.findMaxSumSubarray(arr2, n);
		Console.Write("\n " + result);
	}
}

Output

 9
 14
package main
import "fmt"
/*
    Go Program
    kadane's algorithm for maximum sum subarray
*/

// Returns a maximum value of given number
func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func findMaxSumSubarray(arr[] int, n int) int {
	var bestSum int = 0
	var currentSum int = 0
	for i := 0 ; i < n ; i++ {
		// Sum of subarray
		currentSum = maxValue(0, currentSum + arr[i])
		// Get best result
		bestSum = maxValue(bestSum, currentSum)
	}
	return bestSum
}
func main() {

	// Given array elements
	var arr1 = [] int {1 , 2 , -5 , 1 , 2 , -3 , 3 , -2 , 8}
	var arr2 = [] int {-5, 1, 2, -10, 3, 1, 2, 8, -2 }
	// Test A
	// Get the number of elements
	var n int = len(arr1)
	// [3, -2,  8]
	// Result 9
	var result int = findMaxSumSubarray(arr1, n)
	fmt.Print("\n ", result)
	// Test B
	// Get the number of elements
	n = len(arr2)
	// [3, 1, 2, 8]
	// Result 14
	result = findMaxSumSubarray(arr2, n)
	fmt.Print("\n ", result)
}

Output

 9
 14
<?php
/*
    Php Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray
{
	// Returns a maximum value of given number
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function findMaxSumSubarray($arr, $n)
	{
		$bestSum = 0;
		$currentSum = 0;
		for ($i = 0; $i < $n; ++$i)
		{
			// Sum of subarray
			$currentSum = $this->maxValue(0, $currentSum + $arr[$i]);
			// Get best result
			$bestSum = $this->maxValue($bestSum, $currentSum);
		}
		return $bestSum;
	}
}

function main()
{
	$task = new MaxSubArray();
	// Given array elements
	$arr1 = array(1, 2, -5, 1, 2, -3, 3, -2, 8);
	$arr2 = array(-5, 1, 2, -10, 3, 1, 2, 8, -2);
	// Test A
	// Get the number of elements
	$n = count($arr1);
	// [3, -2,  8]
	// Result 9
	$result = $task->findMaxSumSubarray($arr1, $n);
	echo("\n ".$result);
	// Test B
	// Get the number of elements
	$n = count($arr2);
	// [3, 1, 2, 8]
	// Result 14
	$result = $task->findMaxSumSubarray($arr2, $n);
	echo("\n ".$result);
}
main();

Output

 9
 14
/*
    Node JS Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray
{
	// Returns a maximum value of given number
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	findMaxSumSubarray(arr, n)
	{
		var bestSum = 0;
		var currentSum = 0;
		for (var i = 0; i < n; ++i)
		{
			// Sum of subarray
			currentSum = this.maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = this.maxValue(bestSum, currentSum);
		}
		return bestSum;
	}
}

function main()
{
	var task = new MaxSubArray();
	// Given array elements
	var arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8];
	var arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2];
	// Test A
	// Get the number of elements
	var n = arr1.length;
	// [3, -2,  8]
	// Result 9
	var result = task.findMaxSumSubarray(arr1, n);
	process.stdout.write("\n " + result);
	// Test B
	// Get the number of elements
	n = arr2.length;
	// [3, 1, 2, 8]
	// Result 14
	result = task.findMaxSumSubarray(arr2, n);
	process.stdout.write("\n " + result);
}
main();

Output

 9
 14
#    Python 3 Program
#    kadane's algorithm for maximum sum subarray
class MaxSubArray :
	#  Returns a maximum value of given number
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def findMaxSumSubarray(self, arr, n) :
		bestSum = 0
		currentSum = 0
		i = 0
		while (i < n) :
			#  Sum of sublist
			currentSum = self.maxValue(0, currentSum + arr[i])
			#  Get best result
			bestSum = self.maxValue(bestSum, currentSum)
			i += 1
		
		return bestSum
	

def main() :
	task = MaxSubArray()
	#  Given list elements
	arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8]
	arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2]
	#  Test A
	#  Get the number of elements
	n = len(arr1)
	#  [3, -2,  8]
	#  Result 9
	result = task.findMaxSumSubarray(arr1, n)
	print("\n ", result, end = "")
	#  Test B
	#  Get the number of elements
	n = len(arr2)
	#  [3, 1, 2, 8]
	#  Result 14
	result = task.findMaxSumSubarray(arr2, n)
	print("\n ", result, end = "")

if __name__ == "__main__": main()

Output

  9
  14
#    Ruby Program
#    kadane's algorithm for maximum sum subarray
class MaxSubArray 
	#  Returns a maximum value of given number
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def findMaxSumSubarray(arr, n) 
		bestSum = 0
		currentSum = 0
		i = 0
		while (i < n) 
			#  Sum of subarray
			currentSum = self.maxValue(0, currentSum + arr[i])
			#  Get best result
			bestSum = self.maxValue(bestSum, currentSum)
			i += 1
		end

		return bestSum
	end

end

def main() 
	task = MaxSubArray.new()
	#  Given array elements
	arr1 = [1, 2, -5, 1, 2, -3, 3, -2, 8]
	arr2 = [-5, 1, 2, -10, 3, 1, 2, 8, -2]
	#  Test A
	#  Get the number of elements
	n = arr1.length
	#  [3, -2,  8]
	#  Result 9
	result = task.findMaxSumSubarray(arr1, n)
	print("\n ", result)
	#  Test B
	#  Get the number of elements
	n = arr2.length
	#  [3, 1, 2, 8]
	#  Result 14
	result = task.findMaxSumSubarray(arr2, n)
	print("\n ", result)
end

main()

Output

 9
 14
/*
    Scala Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray()
{
	// Returns a maximum value of given number
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def findMaxSumSubarray(arr: Array[Int], n: Int): Int = {
		var bestSum: Int = 0;
		var currentSum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of subarray
			currentSum = maxValue(0, currentSum + arr(i));
			// Get best result
			bestSum = maxValue(bestSum, currentSum);
			i += 1;
		}
		return bestSum;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MaxSubArray = new MaxSubArray();
		// Given array elements
		var arr1: Array[Int] = Array(1, 2, -5, 1, 2, -3, 3, -2, 8);
		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;
		// [3, -2,  8]
		// Result 9
		var result: Int = task.findMaxSumSubarray(arr1, n);
		print("\n " + result);
		// Test B
		// Get the number of elements
		n = arr2.length;
		// [3, 1, 2, 8]
		// Result 14
		result = task.findMaxSumSubarray(arr2, n);
		print("\n " + result);
	}
}

Output

 9
 14
import Foundation;
/*
    Swift 4 Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray
{
	// Returns a maximum value of given number
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func findMaxSumSubarray(_ arr: [Int], _ n: Int) -> Int
	{
		var bestSum: Int = 0;
		var currentSum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of subarray
			currentSum = self.maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = self.maxValue(bestSum, currentSum);
			i += 1;
		}
		return bestSum;
	}
}
func main()
{
	let task: MaxSubArray = MaxSubArray();
	// Given array elements
	let arr1: [Int] = [1, 2, -5, 1, 2, -3, 3, -2, 8];
	let arr2: [Int] = [-5, 1, 2, -10, 3, 1, 2, 8, -2];
	// Test A
	// Get the number of elements
	var n: Int = arr1.count;
	// [3, -2,  8]
	// Result 9
	var result: Int = task.findMaxSumSubarray(arr1, n);
	print("\n ", result, terminator: "");
	// Test B
	// Get the number of elements
	n = arr2.count;
	// [3, 1, 2, 8]
	// Result 14
	result = task.findMaxSumSubarray(arr2, n);
	print("\n ", result, terminator: "");
}
main();

Output

  9
  14
/*
    Kotlin Program
    kadane's algorithm for maximum sum subarray
*/
class MaxSubArray
{
	// Returns a maximum value of given number
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun findMaxSumSubarray(arr: Array < Int > , n: Int): Int
	{
		var bestSum: Int = 0;
		var currentSum: Int = 0;
		var i: Int = 0;
		while (i < n)
		{
			// Sum of subarray
			currentSum = this.maxValue(0, currentSum + arr[i]);
			// Get best result
			bestSum = this.maxValue(bestSum, currentSum);
			i += 1;
		}
		return bestSum;
	}
}
fun main(args: Array < String > ): Unit
{
	val task: MaxSubArray = MaxSubArray();
	// Given array elements
	val arr1: Array < Int > = arrayOf(1, 2, -5, 1, 2, -3, 3, -2, 8);
	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();
	// [3, -2,  8]
	// Result 9
	var result: Int = task.findMaxSumSubarray(arr1, n);
	print("\n " + result);
	// Test B
	// Get the number of elements
	n = arr2.count();
	// [3, 1, 2, 8]
	// Result 14
	result = task.findMaxSumSubarray(arr2, n);
	print("\n " + result);
}

Output

 9
 14
Last updated on by Kalkicode




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