kadane's algorithm for maximum sum subarray
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