Posted on by Kalkicode
Code Algorithm

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)
{
// 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
System.out.print("\n " + result);
// Test B
// Get the number of elements
n = arr2.length;
// [3, 1, 2, 8]
// Result 14
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()
{
// 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
cout << "\n " << result;
// Test B
// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);
// [3, 1, 2, 8]
// Result 14
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)
{
// 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
Console.Write("\n " + result);
// Test B
// Get the number of elements
n = arr2.Length;
// [3, 1, 2, 8]
// Result 14
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()
{
// 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
echo("\n ".\$result);
// Test B
// Get the number of elements
\$n = count(\$arr2);
// [3, 1, 2, 8]
// Result 14
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()
{
// 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
process.stdout.write("\n " + result);
// Test B
// Get the number of elements
n = arr2.length;
// [3, 1, 2, 8]
// Result 14
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() :
#  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
print("\n ", result, end = "")
#  Test B
#  Get the number of elements
n = len(arr2)
#  [3, 1, 2, 8]
#  Result 14
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()
#  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
print("\n ", result)
#  Test B
#  Get the number of elements
n = arr2.length
#  [3, 1, 2, 8]
#  Result 14
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
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()
{
// 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
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
{
// 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
print("\n " + result);
}``````

Output

`````` 9
14``````

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.

Categories
Relative Post