Posted on by Kalkicode
Code Algorithm

Kadane's Algorithm is a popular algorithm used to find the maximum sum of a contiguous subarray within an array of integers. It is widely used because of its simplicity and efficiency, and can handle both positive and negative numbers.

However, if the array contains only negative numbers, Kadane's Algorithm may not produce the correct output. In such cases, we need to modify the algorithm to handle negative numbers.

The modified algorithm works as follows:

1. Initialize two variables, max_so_far and max_ending_here, to the first element of the array.

2. Traverse the array from the second element to the end.

3. For each element, add it to max_ending_here.

4. If max_ending_here is negative, set it to zero.

5. If max_so_far is less than max_ending_here, set max_so_far to max_ending_here.

6. Repeat steps 3 to 5 until the end of the array is reached.

7. Return max_so_far.

The idea behind this modification is that if we encounter a negative number while traversing the array, adding it to the current subarray can only decrease its sum. Therefore, we reset the current subarray to an empty subarray by setting max_ending_here to zero.

Code Solution

``````// C Program
// kadane's algorithm for all negative numbers
#include <stdio.h>

int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findMaxSumSubarray(int arr[], int n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
int bestSum = 0;
int currentSum = 0;
int auxiliary = arr[0];
int negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (int i = 0; i < n; ++i)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = maxValue(0, currentSum + arr[i]);
bestSum = maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
int main()
{
// Given array elements
int arr1[] = {
-7 , -3 , -5 , -6 , -2 , -8 , -3 , -3 , -9
};
int arr2[] = {
-5 , -1 , -2 , -4 , -3 , -1 , -2 , -2
};
int arr3[] = {
-5 , -1 , -4 , -3 , 1 ,1, -2 , -2
};
// Test A
// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1[0]);
// [-2] max subarray
// Result -2
int result = findMaxSumSubarray(arr1, n);
printf("\n %d", result);
// Test B
// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);
// [-1]  max subarray
// Result -1
result = findMaxSumSubarray(arr2, n);
printf("\n %d", result);
// Test C
// Get the number of elements
n = sizeof(arr3) / sizeof(arr3[0]);
// [1,1]  max subarray
// Result 2
result = findMaxSumSubarray(arr3, n);
printf("\n %d", result);
return 0;
}``````

Output

`````` -2
-1
2``````
``````// Java program for
// kadane's algorithm for all negative numbers
public class SubArray
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findMaxSumSubarray(int[] arr, int n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
int bestSum = 0;
int currentSum = 0;
int auxiliary = arr[0];
int negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (int i = 0; i < n; ++i)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = maxValue(0, currentSum + arr[i]);
bestSum = maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
public static void main(String[] args)
{
// Given array elements
int[] arr1 = {
-7 , -3 , -5 , -6 , -2 , -8 , -3 , -3 , -9
};
int[] arr2 = {
-5 , -1 , -2 , -4 , -3 , -1 , -2 , -2
};
int[] arr3 = {
-5 , -1 , -4 , -3 , 1 , 1 , -2 , -2
};
// Test A
// Get the number of elements
int n = arr1.length;
// [-2] max subarray
// Result -2
System.out.print("\n " + result);
// Test B
// Get the number of elements
n = arr2.length;
// [-1]  max subarray
// Result -1
System.out.print("\n " + result);
// Test C
// Get the number of elements
n = arr3.length;
// [1,1]  max subarray
// Result 2
System.out.print("\n " + result);
}
}``````

Output

`````` -2
-1
2``````
``````// Include header file
#include <iostream>
using namespace std;
// C++ program for
// kadane's algorithm for all negative numbers
class SubArray
{
public: int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
int findMaxSumSubarray(int arr[], int n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
int bestSum = 0;
int currentSum = 0;
int auxiliary = arr[0];
int negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (int i = 0; i < n; ++i)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = this->maxValue(0, currentSum + arr[i]);
bestSum = this->maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
};
int main()
{
// Given array elements
int arr1[] = {
-7 , -3 , -5 , -6 , -2 , -8 , -3 , -3 , -9
};
int arr2[] = {
-5 , -1 , -2 , -4 , -3 , -1 , -2 , -2
};
int arr3[] = {
-5 , -1 , -4 , -3 , 1 , 1 , -2 , -2
};
// Test A
// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1[0]);
// [-2] max subarray
// Result -2
cout << "\n " << result;
// Test B
// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);
// [-1]  max subarray
// Result -1
cout << "\n " << result;
// Test C
// Get the number of elements
n = sizeof(arr3) / sizeof(arr3[0]);
// [1,1]  max subarray
// Result 2
cout << "\n " << result;
return 0;
}``````

Output

`````` -2
-1
2``````
``````// Include namespace system
using System;
// Csharp program for
// kadane's algorithm for all negative numbers
public class SubArray
{
public int maxValue(int a, int b)
{
if (a > b)
{
return a;
}
return b;
}
public int findMaxSumSubarray(int[] arr, int n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
int bestSum = 0;
int currentSum = 0;
int auxiliary = arr[0];
int negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (int i = 0; i < n; ++i)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = this.maxValue(0, currentSum + arr[i]);
bestSum = this.maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
public static void Main(String[] args)
{
// Given array elements
int[] arr1 = {
-7 , -3 , -5 , -6 , -2 , -8 , -3 , -3 , -9
};
int[] arr2 = {
-5 , -1 , -2 , -4 , -3 , -1 , -2 , -2
};
int[] arr3 = {
-5 , -1 , -4 , -3 , 1 , 1 , -2 , -2
};
// Test A
// Get the number of elements
int n = arr1.Length;
// [-2] max subarray
// Result -2
Console.Write("\n " + result);
// Test B
// Get the number of elements
n = arr2.Length;
// [-1]  max subarray
// Result -1
Console.Write("\n " + result);
// Test C
// Get the number of elements
n = arr3.Length;
// [1,1]  max subarray
// Result 2
Console.Write("\n " + result);
}
}``````

Output

`````` -2
-1
2``````
``````package main
import "fmt"
// Go program for
// kadane's algorithm for all negative numbers
type SubArray struct {}
func getSubArray() * SubArray {
var me *SubArray = &SubArray {}
return me
}
func(this SubArray) maxValue(a, b int) int {
if a > b {
return a
}
return b
}
func(this SubArray) findMaxSumSubarray(arr[] int, n int) int {
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
var bestSum int = 0
var currentSum int = 0
var auxiliary int = arr[0]
var negative int = 1
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for i := 0 ; i < n ; i++ {
if arr[i] >= 0 {
// When array contains positive value
negative = 0
}
currentSum = this.maxValue(0, currentSum + arr[i])
bestSum = this.maxValue(bestSum, currentSum)
if auxiliary < arr[i] {
auxiliary = arr[i]
}
}
if negative == 1 {
return auxiliary
}
return bestSum
}
func main() {
var task * SubArray = getSubArray()
// Given array elements
var arr1 = [] int { -7, -3, -5, -6, -2, -8, -3, -3, -9 }
var arr2 = [] int { -5, -1, -2, -4, -3, -1, -2, -2 }
var arr3 = [] int { -5, -1, -4, -3, 1, 1, -2, -2 }
// Test A
// Get the number of elements
var n int = len(arr1)
// [-2] max subarray
// Result -2
var result int = task.findMaxSumSubarray(arr1, n)
fmt.Print("\n ", result)
// Test B
// Get the number of elements
n = len(arr2)
// [-1]  max subarray
// Result -1
fmt.Print("\n ", result)
// Test C
// Get the number of elements
n = len(arr3)
// [1,1]  max subarray
// Result 2
fmt.Print("\n ", result)
}``````

Output

`````` -2
-1
2``````
``````<?php
// Php program for
// kadane's algorithm for all negative numbers
class SubArray
{
public	function maxValue(\$a, \$b)
{
if (\$a > \$b)
{
return \$a;
}
return \$b;
}
public	function findMaxSumSubarray(\$arr, \$n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
\$bestSum = 0;
\$currentSum = 0;
\$auxiliary = \$arr[0];
\$negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$arr[\$i] >= 0)
{
// When array contains positive value
\$negative = 0;
}
\$currentSum = \$this->maxValue(0, \$currentSum + \$arr[\$i]);
\$bestSum = \$this->maxValue(\$bestSum, \$currentSum);
if (\$auxiliary < \$arr[\$i])
{
\$auxiliary = \$arr[\$i];
}
}
if (\$negative == 1)
{
return \$auxiliary;
}
return \$bestSum;
}
}

function main()
{
// Given array elements
\$arr1 = array(-7, -3, -5, -6, -2, -8, -3, -3, -9);
\$arr2 = array(-5, -1, -2, -4, -3, -1, -2, -2);
\$arr3 = array(-5, -1, -4, -3, 1, 1, -2, -2);
// Test A
// Get the number of elements
\$n = count(\$arr1);
// [-2] max subarray
// Result -2
echo("\n ".\$result);
// Test B
// Get the number of elements
\$n = count(\$arr2);
// [-1]  max subarray
// Result -1
echo("\n ".\$result);
// Test C
// Get the number of elements
\$n = count(\$arr3);
// [1,1]  max subarray
// Result 2
echo("\n ".\$result);
}
main();``````

Output

`````` -2
-1
2``````
``````// Node JS program for
// kadane's algorithm for all negative numbers
class SubArray
{
maxValue(a, b)
{
if (a > b)
{
return a;
}
return b;
}
findMaxSumSubarray(arr, n)
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
var bestSum = 0;
var currentSum = 0;
var auxiliary = arr[0];
var negative = 1;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
for (var i = 0; i < n; ++i)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = this.maxValue(0, currentSum + arr[i]);
bestSum = this.maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
}

function main()
{
// Given array elements
var arr1 = [-7, -3, -5, -6, -2, -8, -3, -3, -9];
var arr2 = [-5, -1, -2, -4, -3, -1, -2, -2];
var arr3 = [-5, -1, -4, -3, 1, 1, -2, -2];
// Test A
// Get the number of elements
var n = arr1.length;
// [-2] max subarray
// Result -2
process.stdout.write("\n " + result);
// Test B
// Get the number of elements
n = arr2.length;
// [-1]  max subarray
// Result -1
process.stdout.write("\n " + result);
// Test C
// Get the number of elements
n = arr3.length;
// [1,1]  max subarray
// Result 2
process.stdout.write("\n " + result);
}
main();``````

Output

`````` -2
-1
2``````
``````#  Python 3 program for
#  kadane's algorithm for all negative numbers
class SubArray :
def maxValue(self, a, b) :
if (a > b) :
return a

return b

def findMaxSumSubarray(self, arr, n) :
#  If the list contains all non-positive numbers.
#  Then the solution is the number in
#  the list with the smallest value.
bestSum = 0
currentSum = 0
auxiliary = arr[0]
negative = 1
i = 0
#  Below implement process are handle all negative numbers,
#  and as well as positive and negative number combination.
while (i < n) :
if (arr[i] >= 0) :
#  When list contains positive value
negative = 0

currentSum = self.maxValue(0, currentSum + arr[i])
bestSum = self.maxValue(bestSum, currentSum)
if (auxiliary < arr[i]) :
auxiliary = arr[i]

i += 1

if (negative == 1) :
return auxiliary

return bestSum

def main() :
#  Given list elements
arr1 = [-7, -3, -5, -6, -2, -8, -3, -3, -9]
arr2 = [-5, -1, -2, -4, -3, -1, -2, -2]
arr3 = [-5, -1, -4, -3, 1, 1, -2, -2]
#  Test A
#  Get the number of elements
n = len(arr1)
#  [-2] max sublist
#  Result -2
print("\n ", result, end = "")
#  Test B
#  Get the number of elements
n = len(arr2)
#  [-1]  max sublist
#  Result -1
print("\n ", result, end = "")
#  Test C
#  Get the number of elements
n = len(arr3)
#  [1,1]  max sublist
#  Result 2
print("\n ", result, end = "")

if __name__ == "__main__": main()``````

Output

``````  -2
-1
2``````
``````#  Ruby program for
#  kadane's algorithm for all negative numbers
class SubArray
def maxValue(a, b)
if (a > b)
return a
end

return b
end

def findMaxSumSubarray(arr, n)
#  If the array contains all non-positive numbers.
#  Then the solution is the number in
#  the array with the smallest value.
bestSum = 0
currentSum = 0
auxiliary = arr[0]
negative = 1
i = 0
#  Below implement process are handle all negative numbers,
#  and as well as positive and negative number combination.
while (i < n)
if (arr[i] >= 0)
#  When array contains positive value
negative = 0
end

currentSum = self.maxValue(0, currentSum + arr[i])
bestSum = self.maxValue(bestSum, currentSum)
if (auxiliary < arr[i])
auxiliary = arr[i]
end

i += 1
end

if (negative == 1)
return auxiliary
end

return bestSum
end

end

def main()
#  Given array elements
arr1 = [-7, -3, -5, -6, -2, -8, -3, -3, -9]
arr2 = [-5, -1, -2, -4, -3, -1, -2, -2]
arr3 = [-5, -1, -4, -3, 1, 1, -2, -2]
#  Test A
#  Get the number of elements
n = arr1.length
#  [-2] max subarray
#  Result -2
print("\n ", result)
#  Test B
#  Get the number of elements
n = arr2.length
#  [-1]  max subarray
#  Result -1
print("\n ", result)
#  Test C
#  Get the number of elements
n = arr3.length
#  [1,1]  max subarray
#  Result 2
print("\n ", result)
end

main()``````

Output

`````` -2
-1
2``````
``````// Scala program for
// kadane's algorithm for all negative numbers
class SubArray()
{
def maxValue(a: Int, b: Int): Int = {
if (a > b)
{
return a;
}
return b;
}
def findMaxSumSubarray(arr: Array[Int], n: Int): Int = {
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
var bestSum: Int = 0;
var currentSum: Int = 0;
var auxiliary: Int = arr(0);
var negative: Int = 1;
var i: Int = 0;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
while (i < n)
{
if (arr(i) >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = maxValue(0, currentSum + arr(i));
bestSum = maxValue(bestSum, currentSum);
if (auxiliary < arr(i))
{
auxiliary = arr(i);
}
i += 1;
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: SubArray = new SubArray();
// Given array elements
var arr1: Array[Int] = Array(-7, -3, -5, -6, -2, -8, -3, -3, -9);
var arr2: Array[Int] = Array(-5, -1, -2, -4, -3, -1, -2, -2);
var arr3: Array[Int] = Array(-5, -1, -4, -3, 1, 1, -2, -2);
// Test A
// Get the number of elements
var n: Int = arr1.length;
// [-2] max subarray
// Result -2
var result: Int = task.findMaxSumSubarray(arr1, n);
print("\n " + result);
// Test B
// Get the number of elements
n = arr2.length;
// [-1]  max subarray
// Result -1
print("\n " + result);
// Test C
// Get the number of elements
n = arr3.length;
// [1,1]  max subarray
// Result 2
print("\n " + result);
}
}``````

Output

`````` -2
-1
2``````
``````import Foundation;
// Swift 4 program for
// kadane's algorithm for all negative numbers
class SubArray
{
func maxValue(_ a: Int, _ b: Int) -> Int
{
if (a > b)
{
return a;
}
return b;
}
func findMaxSumSubarray(_ arr: [Int], _ n: Int) -> Int
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
var bestSum: Int = 0;
var currentSum: Int = 0;
var auxiliary: Int = arr[0];
var negative: Int = 1;
var i: Int = 0;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
while (i < n)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = self.maxValue(0, currentSum + arr[i]);
bestSum = self.maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
i += 1;
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
}
func main()
{
// Given array elements
let arr1: [Int] = [-7, -3, -5, -6, -2, -8, -3, -3, -9];
let arr2: [Int] = [-5, -1, -2, -4, -3, -1, -2, -2];
let arr3: [Int] = [-5, -1, -4, -3, 1, 1, -2, -2];
// Test A
// Get the number of elements
var n: Int = arr1.count;
// [-2] max subarray
// Result -2
var result: Int = task.findMaxSumSubarray(arr1, n);
print("\n ", result, terminator: "");
// Test B
// Get the number of elements
n = arr2.count;
// [-1]  max subarray
// Result -1
print("\n ", result, terminator: "");
// Test C
// Get the number of elements
n = arr3.count;
// [1,1]  max subarray
// Result 2
print("\n ", result, terminator: "");
}
main();``````

Output

``````  -2
-1
2``````
``````// Kotlin program for
// kadane's algorithm for all negative numbers
class SubArray
{
fun maxValue(a: Int, b: Int): Int
{
if (a > b)
{
return a;
}
return b;
}
fun findMaxSumSubarray(arr: Array < Int > , n: Int): Int
{
// If the array contains all non-positive numbers.
// Then the solution is the number in
// the array with the smallest value.
var bestSum: Int = 0;
var currentSum: Int = 0;
var auxiliary: Int = arr[0];
var negative: Int = 1;
var i: Int = 0;
// Below implement process are handle all negative numbers,
// and as well as positive and negative number combination.
while (i < n)
{
if (arr[i] >= 0)
{
// When array contains positive value
negative = 0;
}
currentSum = this.maxValue(0, currentSum + arr[i]);
bestSum = this.maxValue(bestSum, currentSum);
if (auxiliary < arr[i])
{
auxiliary = arr[i];
}
i += 1;
}
if (negative == 1)
{
return auxiliary;
}
return bestSum;
}
}
fun main(args: Array < String > ): Unit
{
// Given array elements
val arr1: Array < Int > = arrayOf(-7, -3, -5, -6, -2, -8, -3, -3, -9);
val arr2: Array < Int > = arrayOf(-5, -1, -2, -4, -3, -1, -2, -2);
val arr3: Array < Int > = arrayOf(-5, -1, -4, -3, 1, 1, -2, -2);
// Test A
// Get the number of elements
var n: Int = arr1.count();
// [-2] max subarray
// Result -2
var result: Int = task.findMaxSumSubarray(arr1, n);
print("\n " + result);
// Test B
// Get the number of elements
n = arr2.count();
// [-1]  max subarray
// Result -1
print("\n " + result);
// Test C
// Get the number of elements
n = arr3.count();
// [1,1]  max subarray
// Result 2
print("\n " + result);
}``````

Output

`````` -2
-1
2``````

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