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