Skip to main content

kadane's algorithm for negative numbers

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)
	{
		SubArray task = new SubArray();
		// 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
		int result = task.findMaxSumSubarray(arr1, n);
		System.out.print("\n " + result);
		// Test B
		// Get the number of elements
		n = arr2.length;
		// [-1]  max subarray
		// Result -1
		result = task.findMaxSumSubarray(arr2, n);
		System.out.print("\n " + result);
		// Test C
		// Get the number of elements
		n = arr3.length;
		// [1,1]  max subarray
		// Result 2
		result = task.findMaxSumSubarray(arr3, n);
		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()
{
	SubArray *task = new SubArray();
	// 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 = task->findMaxSumSubarray(arr1, n);
	cout << "\n " << result;
	// Test B
	// Get the number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [-1]  max subarray
	// Result -1
	result = task->findMaxSumSubarray(arr2, n);
	cout << "\n " << result;
	// Test C
	// Get the number of elements
	n = sizeof(arr3) / sizeof(arr3[0]);
	// [1,1]  max subarray
	// Result 2
	result = task->findMaxSumSubarray(arr3, n);
	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)
	{
		SubArray task = new SubArray();
		// 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
		int result = task.findMaxSumSubarray(arr1, n);
		Console.Write("\n " + result);
		// Test B
		// Get the number of elements
		n = arr2.Length;
		// [-1]  max subarray
		// Result -1
		result = task.findMaxSumSubarray(arr2, n);
		Console.Write("\n " + result);
		// Test C
		// Get the number of elements
		n = arr3.Length;
		// [1,1]  max subarray
		// Result 2
		result = task.findMaxSumSubarray(arr3, n);
		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
	result = task.findMaxSumSubarray(arr2, n)
	fmt.Print("\n ", result)
	// Test C
	// Get the number of elements
	n = len(arr3)
	// [1,1]  max subarray
	// Result 2
	result = task.findMaxSumSubarray(arr3, n)
	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()
{
	$task = new SubArray();
	// 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
	$result = $task->findMaxSumSubarray($arr1, $n);
	echo("\n ".$result);
	// Test B
	// Get the number of elements
	$n = count($arr2);
	// [-1]  max subarray
	// Result -1
	$result = $task->findMaxSumSubarray($arr2, $n);
	echo("\n ".$result);
	// Test C
	// Get the number of elements
	$n = count($arr3);
	// [1,1]  max subarray
	// Result 2
	$result = $task->findMaxSumSubarray($arr3, $n);
	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()
{
	var task = new SubArray();
	// 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
	var result = task.findMaxSumSubarray(arr1, n);
	process.stdout.write("\n " + result);
	// Test B
	// Get the number of elements
	n = arr2.length;
	// [-1]  max subarray
	// Result -1
	result = task.findMaxSumSubarray(arr2, n);
	process.stdout.write("\n " + result);
	// Test C
	// Get the number of elements
	n = arr3.length;
	// [1,1]  max subarray
	// Result 2
	result = task.findMaxSumSubarray(arr3, n);
	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() :
	task = SubArray()
	#  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
	result = task.findMaxSumSubarray(arr1, n)
	print("\n ", result, end = "")
	#  Test B
	#  Get the number of elements
	n = len(arr2)
	#  [-1]  max sublist
	#  Result -1
	result = task.findMaxSumSubarray(arr2, n)
	print("\n ", result, end = "")
	#  Test C
	#  Get the number of elements
	n = len(arr3)
	#  [1,1]  max sublist
	#  Result 2
	result = task.findMaxSumSubarray(arr3, n)
	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() 
	task = SubArray.new()
	#  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
	result = task.findMaxSumSubarray(arr1, n)
	print("\n ", result)
	#  Test B
	#  Get the number of elements
	n = arr2.length
	#  [-1]  max subarray
	#  Result -1
	result = task.findMaxSumSubarray(arr2, n)
	print("\n ", result)
	#  Test C
	#  Get the number of elements
	n = arr3.length
	#  [1,1]  max subarray
	#  Result 2
	result = task.findMaxSumSubarray(arr3, n)
	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
		result = task.findMaxSumSubarray(arr2, n);
		print("\n " + result);
		// Test C
		// Get the number of elements
		n = arr3.length;
		// [1,1]  max subarray
		// Result 2
		result = task.findMaxSumSubarray(arr3, n);
		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()
{
	let task: SubArray = SubArray();
	// 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
	result = task.findMaxSumSubarray(arr2, n);
	print("\n ", result, terminator: "");
	// Test C
	// Get the number of elements
	n = arr3.count;
	// [1,1]  max subarray
	// Result 2
	result = task.findMaxSumSubarray(arr3, n);
	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
{
	val task: SubArray = SubArray();
	// 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
	result = task.findMaxSumSubarray(arr2, n);
	print("\n " + result);
	// Test C
	// Get the number of elements
	n = arr3.count();
	// [1,1]  max subarray
	// Result 2
	result = task.findMaxSumSubarray(arr3, n);
	print("\n " + result);
}

Output

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