Skip to main content

Maximum sum subarray using divide and conquer

The maximum sum subarray problem involves finding the contiguous subarray with the largest sum within an array of integers. One approach to solving this problem is using a divide and conquer algorithm, which works by recursively dividing the input array into two halves, finding the maximum subarray sum in each half, and then combining these results to find the maximum subarray sum in the original array.

Here given code implementation process.

/*
    C program for
    Maximum sum subarray using divide and conquer
*/
#include <stdio.h>
#include <limits.h>

// Display given array elements
void printArray(int arr[], int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf(" %d", arr[i]);
	}
}
// Returns the maximum value of given two numbers
int maxValue(int a, int b)
{
	if (a > b)
	{
		return a;
	}
	return b;
}
int maxSum(int arr[], int low, int middle, int high)
{
	// Contain sum of left and right subarray
	int leftSum = INT_MIN;
	int rightSum = INT_MIN;
	int sum = 0;
	// Calculate left subarray sum
	for (int i = middle; i >= low; --i)
	{
		// Current sum
		sum = sum + arr[i];
		if (sum > leftSum)
		{
			leftSum = sum;
		}
	}
	sum = 0;
	// Calculate right subarray sum
	for (int i = middle + 1; i <= high; ++i)
	{
		// Current sum
		sum = sum + arr[i];
		if (sum > rightSum)
		{
			rightSum = sum;
		}
	}
	return maxValue(maxValue(leftSum + rightSum, leftSum), rightSum);
}
int maxSubArraySum(int arr[], int low, int high)
{
	// Base Case: Only one element 
	if (low == high)
	{
		return arr[low];
	}
	// Find middle point 
	int middle = (low + high) / 2;
	// Calculate the sum of left subarray from (low to middle).
	int a = maxSubArraySum(arr, low, middle);
	// Calculate the sum of middle subarray from (middle to high).
	int b = maxSum(arr, low, middle, high);
	// Calculate the sum of right subarray from (middle+1 to high).
	int c = maxSubArraySum(arr, middle + 1, high);
	return maxValue(maxValue(a, b), c);
}
//  Handles the request of  finding max sum subarray
void findMaxSumSubarray(int arr[], int n)
{
	// Display array elements
	printArray(arr, n);
	// Get max subarray sum
	int sum = maxSubArraySum(arr, 0, n - 1);
	// Display calculated sum
	printf("\n Maximum sum subarray : %d \n", sum);
}
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
	findMaxSumSubarray(arr1, n);
	// Test B
	// Get the number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3, 1, 2, 8]
	// Result 14
	findMaxSumSubarray(arr2, n);
	return 0;
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
/*
    Java Program for
    Maximum sum subarray using divide and conquer
*/
public class MaximumSubarray
{
	// Display given array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			System.out.print(" " + arr[i]);
		}
	}
	// Returns the maximum value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int maxSum(int[] arr, int low, int middle, int high)
	{
		// Contain sum of left and right subarray
		int leftSum = Integer.MIN_VALUE;
		int rightSum = Integer.MIN_VALUE;
		int sum = 0;
		// Calculate left subarray sum
		for (int i = middle; i >= low; --i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
		}
		sum = 0;
		// Calculate right subarray sum
		for (int i = middle + 1; i <= high; ++i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
		}
		return maxValue(maxValue(leftSum + rightSum, leftSum), rightSum);
	}
	public int maxSubArraySum(int[] arr, int low, int high)
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		int middle = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		int a = maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		int b = maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		int c = maxSubArraySum(arr, middle + 1, high);
		return maxValue(maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	public void findMaxSumSubarray(int[] arr, int n)
	{
		// Display array elements
		printArray(arr, n);
		// Get max subarray sum
		int sum = maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		System.out.print("\n Maximum sum subarray : " + sum + " \n");
	}
	public static void main(String[] args)
	{
		MaximumSubarray task = new MaximumSubarray();
		// 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
		task.findMaxSumSubarray(arr1, n);
		// Test B
		// Get the number of elements
		n = arr2.length;
		// [3, 1, 2, 8]
		// Result 14
		task.findMaxSumSubarray(arr2, n);
	}
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
// Include header file
#include <iostream>
#include <limits.h>

using namespace std;
/*
    C++ Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray
{
	public:
		// Display given array elements
		void printArray(int arr[], int n)
		{
			for (int i = 0; i < n; ++i)
			{
				cout << " " << arr[i];
			}
		}
	// Returns the maximum value of given two numbers
	int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	int maxSum(int arr[], int low, int middle, int high)
	{
		// Contain sum of left and right subarray
		int leftSum = INT_MIN;
		int rightSum = INT_MIN;
		int sum = 0;
		// Calculate left subarray sum
		for (int i = middle; i >= low; --i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
		}
		sum = 0;
		// Calculate right subarray sum
		for (int i = middle + 1; i <= high; ++i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
		}
		return this->maxValue(this->maxValue(leftSum + rightSum, leftSum), rightSum);
	}
	int maxSubArraySum(int arr[], int low, int high)
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		int middle = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		int a = this->maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		int b = this->maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		int c = this->maxSubArraySum(arr, middle + 1, high);
		return this->maxValue(this->maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	void findMaxSumSubarray(int arr[], int n)
	{
		// Display array elements
		this->printArray(arr, n);
		// Get max subarray sum
		int sum = this->maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		cout << "\n Maximum sum subarray : " << sum << " \n";
	}
};
int main()
{
	MaximumSubarray *task = new MaximumSubarray();
	// 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
	task->findMaxSumSubarray(arr1, n);
	// Test B
	// Get the number of elements
	n = sizeof(arr2) / sizeof(arr2[0]);
	// [3, 1, 2, 8]
	// Result 14
	task->findMaxSumSubarray(arr2, n);
	return 0;
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
// Include namespace system
using System;
/*
    Csharp Program for
    Maximum sum subarray using divide and conquer
*/
public class MaximumSubarray
{
	// Display given array elements
	public void printArray(int[] arr, int n)
	{
		for (int i = 0; i < n; ++i)
		{
			Console.Write(" " + arr[i]);
		}
	}
	// Returns the maximum value of given two numbers
	public int maxValue(int a, int b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	public int maxSum(int[] arr, int low, int middle, int high)
	{
		// Contain sum of left and right subarray
		int leftSum = int.MinValue;
		int rightSum = int.MinValue;
		int sum = 0;
		// Calculate left subarray sum
		for (int i = middle; i >= low; --i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
		}
		sum = 0;
		// Calculate right subarray sum
		for (int i = middle + 1; i <= high; ++i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
		}
		return this.maxValue(this.maxValue(leftSum + rightSum, leftSum), rightSum);
	}
	public int maxSubArraySum(int[] arr, int low, int high)
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		int middle = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		int a = this.maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		int b = this.maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		int c = this.maxSubArraySum(arr, middle + 1, high);
		return this.maxValue(this.maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	public void findMaxSumSubarray(int[] arr, int n)
	{
		// Display array elements
		this.printArray(arr, n);
		// Get max subarray sum
		int sum = this.maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		Console.Write("\n Maximum sum subarray : " + sum + " \n");
	}
	public static void Main(String[] args)
	{
		MaximumSubarray task = new MaximumSubarray();
		// 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
		task.findMaxSumSubarray(arr1, n);
		// Test B
		// Get the number of elements
		n = arr2.Length;
		// [3, 1, 2, 8]
		// Result 14
		task.findMaxSumSubarray(arr2, n);
	}
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
package main
import "math"
import "fmt"
/*
    Go Program for
    Maximum sum subarray using divide and conquer
*/

// Display given array elements
func printArray(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print(" ", arr[i])
	}
}
// Returns the maximum value of given two numbers
func maxValue(a, b int) int {
	if a > b {
		return a
	}
	return b
}
func maxSum(arr[] int, low int, middle int, high int) int {
	// Contain sum of left and right subarray
	var leftSum int = math.MinInt64
	var rightSum int = math.MinInt64
	var sum int = 0
	// Calculate left subarray sum
	for i := middle ; i >= low ; i-- {
		// Current sum
		sum = sum + arr[i]
		if sum > leftSum {
			leftSum = sum
		}
	}
	sum = 0
	// Calculate right subarray sum
	for i := middle + 1 ; i <= high ; i++ {
		// Current sum
		sum = sum + arr[i]
		if sum > rightSum {
			rightSum = sum
		}
	}
	return maxValue(maxValue(leftSum + rightSum, leftSum), rightSum)
}
func maxSubArraySum(arr[] int, low int, high int) int {
	// Base Case: Only one element 
	if low == high {
		return arr[low]
	}
	// Find middle point 
	var middle int = (low + high) / 2
	// Calculate the sum of left subarray from (low to middle).
	var a int = maxSubArraySum(arr, low, middle)
	// Calculate the sum of middle subarray from (middle to high).
	var b int = maxSum(arr, low, middle, high)
	// Calculate the sum of right subarray from (middle+1 to high).
	var c int = maxSubArraySum(arr, middle + 1, high)
	return maxValue(maxValue(a, b), c)
}
//  Handles the request of  finding max sum subarray
func findMaxSumSubarray(arr[] int, n int) {
	// Display array elements
	printArray(arr, n)
	// Get max subarray sum
	var sum int = maxSubArraySum(arr, 0, n - 1)
	// Display calculated sum
	fmt.Print("\n Maximum sum subarray : ", sum, " \n")
}
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
	findMaxSumSubarray(arr1, n)
	// Test B
	// Get the number of elements
	n = len(arr2)
	// [3, 1, 2, 8]
	// Result 14
	findMaxSumSubarray(arr2, n)
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
<?php
/*
    Php Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray
{
	// Display given array elements
	public	function printArray($arr, $n)
	{
		for ($i = 0; $i < $n; ++$i)
		{
			echo(" ".$arr[$i]);
		}
	}
	// Returns the maximum value of given two numbers
	public	function maxValue($a, $b)
	{
		if ($a > $b)
		{
			return $a;
		}
		return $b;
	}
	public	function maxSum($arr, $low, $middle, $high)
	{
		// Contain sum of left and right subarray
		$leftSum = -PHP_INT_MAX;
		$rightSum = -PHP_INT_MAX;
		$sum = 0;
		// Calculate left subarray sum
		for ($i = $middle; $i >= $low; --$i)
		{
			// Current sum
			$sum = $sum + $arr[$i];
			if ($sum > $leftSum)
			{
				$leftSum = $sum;
			}
		}
		$sum = 0;
		// Calculate right subarray sum
		for ($i = $middle + 1; $i <= $high; ++$i)
		{
			// Current sum
			$sum = $sum + $arr[$i];
			if ($sum > $rightSum)
			{
				$rightSum = $sum;
			}
		}
		return $this->maxValue(
          	   $this->maxValue($leftSum + $rightSum, $leftSum), 
               $rightSum);
	}
	public	function maxSubArraySum($arr, $low, $high)
	{
		// Base Case: Only one element 
		if ($low == $high)
		{
			return $arr[$low];
		}
		// Find middle point 
		$middle = (int)(($low + $high) / 2);
		// Calculate the sum of left subarray from (low to middle).
		$a = $this->maxSubArraySum($arr, $low, $middle);
		// Calculate the sum of middle subarray from (middle to high).
		$b = $this->maxSum($arr, $low, $middle, $high);
		// Calculate the sum of right subarray from (middle+1 to high).
		$c = $this->maxSubArraySum($arr, $middle + 1, $high);
		return $this->maxValue($this->maxValue($a, $b), $c);
	}
	//  Handles the request of  finding max sum subarray
	public	function findMaxSumSubarray($arr, $n)
	{
		// Display array elements
		$this->printArray($arr, $n);
		// Get max subarray sum
		$sum = $this->maxSubArraySum($arr, 0, $n - 1);
		// Display calculated sum
		echo("\n Maximum sum subarray : ".$sum." \n");
	}
}

function main()
{
	$task = new MaximumSubarray();
	// 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
	$task->findMaxSumSubarray($arr1, $n);
	// Test B
	// Get the number of elements
	$n = count($arr2);
	// [3, 1, 2, 8]
	// Result 14
	$task->findMaxSumSubarray($arr2, $n);
}
main();

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
/*
    Node JS Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray
{
	// Display given array elements
	printArray(arr, n)
	{
		for (var i = 0; i < n; ++i)
		{
			process.stdout.write(" " + arr[i]);
		}
	}
	// Returns the maximum value of given two numbers
	maxValue(a, b)
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	maxSum(arr, low, middle, high)
	{
		// Contain sum of left and right subarray
		var leftSum = -Number.MAX_VALUE;
		var rightSum = -Number.MAX_VALUE;
		var sum = 0;
		// Calculate left subarray sum
		for (var i = middle; i >= low; --i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
		}
		sum = 0;
		// Calculate right subarray sum
		for (var i = middle + 1; i <= high; ++i)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
		}
		return this.maxValue(
          this.maxValue(leftSum + rightSum, leftSum), 
          rightSum);
	}
	maxSubArraySum(arr, low, high)
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		var middle = parseInt((low + high) / 2);
		// Calculate the sum of left subarray from (low to middle).
		var a = this.maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		var b = this.maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		var c = this.maxSubArraySum(arr, middle + 1, high);
		return this.maxValue(this.maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	findMaxSumSubarray(arr, n)
	{
		// Display array elements
		this.printArray(arr, n);
		// Get max subarray sum
		var sum = this.maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		process.stdout.write("\n Maximum sum subarray : " + sum + " \n");
	}
}

function main()
{
	var task = new MaximumSubarray();
	// 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
	task.findMaxSumSubarray(arr1, n);
	// Test B
	// Get the number of elements
	n = arr2.length;
	// [3, 1, 2, 8]
	// Result 14
	task.findMaxSumSubarray(arr2, n);
}
main();

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
import sys
#    Python 3 Program for
#    Maximum sum subarray using divide and conquer
class MaximumSubarray :
	#  Display given list elements
	def printArray(self, arr, n) :
		i = 0
		while (i < n) :
			print(" ", arr[i], end = "")
			i += 1
		
	
	#  Returns the maximum value of given two numbers
	def maxValue(self, a, b) :
		if (a > b) :
			return a
		
		return b
	
	def maxSum(self, arr, low, middle, high) :
		#  Contain sum of left and right sublist
		leftSum = -sys.maxsize
		rightSum = -sys.maxsize
		sum = 0
		i = middle
		#  Calculate left sublist sum
		while (i >= low) :
			#  Current sum
			sum = sum + arr[i]
			if (sum > leftSum) :
				leftSum = sum
			
			i -= 1
		
		sum = 0
		i = middle + 1
		#  Calculate right sublist sum
		while (i <= high) :
			#  Current sum
			sum = sum + arr[i]
			if (sum > rightSum) :
				rightSum = sum
			
			i += 1
		
		return self.maxValue(
          self.maxValue(leftSum + rightSum, leftSum), rightSum)
	
	def maxSubArraySum(self, arr, low, high) :
		#  Base Case: Only one element 
		if (low == high) :
			return arr[low]
		
		#  Find middle point 
		middle = int((low + high) / 2)
		#  Calculate the sum of left sublist from (low to middle).
		a = self.maxSubArraySum(arr, low, middle)
		#  Calculate the sum of middle sublist from (middle to high).
		b = self.maxSum(arr, low, middle, high)
		#  Calculate the sum of right sublist from (middle+1 to high).
		c = self.maxSubArraySum(arr, middle + 1, high)
		return self.maxValue(self.maxValue(a, b), c)
	
	#   Handles the request of  finding max sum sublist
	def findMaxSumSubarray(self, arr, n) :
		#  Display list elements
		self.printArray(arr, n)
		#  Get max sublist sum
		sum = self.maxSubArraySum(arr, 0, n - 1)
		#  Display calculated sum
		print("\n Maximum sum subarray : ", sum ," ")
	

def main() :
	task = MaximumSubarray()
	#  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
	task.findMaxSumSubarray(arr1, n)
	#  Test B
	#  Get the number of elements
	n = len(arr2)
	#  [3, 1, 2, 8]
	#  Result 14
	task.findMaxSumSubarray(arr2, n)

if __name__ == "__main__": main()

Output

  1  2  -5  1  2  -3  3  -2  8
 Maximum sum subarray :  9
  -5  1  2  -10  3  1  2  8  -2
 Maximum sum subarray :  14
#    Ruby Program for
#    Maximum sum subarray using divide and conquer
class MaximumSubarray 
	#  Display given array elements
	def printArray(arr, n) 
		i = 0
		while (i < n) 
			print(" ", arr[i])
			i += 1
		end

	end

	#  Returns the maximum value of given two numbers
	def maxValue(a, b) 
		if (a > b) 
			return a
		end

		return b
	end

	def maxSum(arr, low, middle, high) 
		#  Contain sum of left and right subarray
		leftSum = -(2 ** (0. size * 8 - 2))
		rightSum = -(2 ** (0. size * 8 - 2))
		sum = 0
		i = middle
		#  Calculate left subarray sum
		while (i >= low) 
			#  Current sum
			sum = sum + arr[i]
			if (sum > leftSum) 
				leftSum = sum
			end

			i -= 1
		end

		sum = 0
		i = middle + 1
		#  Calculate right subarray sum
		while (i <= high) 
			#  Current sum
			sum = sum + arr[i]
			if (sum > rightSum) 
				rightSum = sum
			end

			i += 1
		end

		return self.maxValue(
          self.maxValue(leftSum + rightSum, leftSum), rightSum)
	end

	def maxSubArraySum(arr, low, high) 
		#  Base Case: Only one element 
		if (low == high) 
			return arr[low]
		end

		#  Find middle point 
		middle = (low + high) / 2
		#  Calculate the sum of left subarray from (low to middle).
		a = self.maxSubArraySum(arr, low, middle)
		#  Calculate the sum of middle subarray from (middle to high).
		b = self.maxSum(arr, low, middle, high)
		#  Calculate the sum of right subarray from (middle+1 to high).
		c = self.maxSubArraySum(arr, middle + 1, high)
		return self.maxValue(self.maxValue(a, b), c)
	end

	#   Handles the request of  finding max sum subarray
	def findMaxSumSubarray(arr, n) 
		#  Display array elements
		self.printArray(arr, n)
		#  Get max subarray sum
		sum = self.maxSubArraySum(arr, 0, n - 1)
		#  Display calculated sum
		print("\n Maximum sum subarray : ", sum ," \n")
	end

end

def main() 
	task = MaximumSubarray.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
	task.findMaxSumSubarray(arr1, n)
	#  Test B
	#  Get the number of elements
	n = arr2.length
	#  [3, 1, 2, 8]
	#  Result 14
	task.findMaxSumSubarray(arr2, n)
end

main()

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9 
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14 

/*
    Scala Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray()
{
	// Display given array elements
	def printArray(arr: Array[Int], n: Int): Unit = {
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr(i));
			i += 1;
		}
	}
	// Returns the maximum value of given two numbers
	def maxValue(a: Int, b: Int): Int = {
		if (a > b)
		{
			return a;
		}
		return b;
	}
	def maxSum(arr: Array[Int], low: Int, middle: Int, high: Int): Int = {
		// Contain sum of left and right subarray
		var leftSum: Int = Int.MinValue;
		var rightSum: Int = Int.MinValue;
		var sum: Int = 0;
		var i: Int = middle;
		// Calculate left subarray sum
		while (i >= low)
		{
			// Current sum
			sum = sum + arr(i);
			if (sum > leftSum)
			{
				leftSum = sum;
			}
			i -= 1;
		}
		sum = 0;
		i = middle + 1;
		// Calculate right subarray sum
		while (i <= high)
		{
			// Current sum
			sum = sum + arr(i);
			if (sum > rightSum)
			{
				rightSum = sum;
			}
			i += 1;
		}
		return maxValue(
          maxValue(leftSum + rightSum, leftSum), 
          rightSum);
	}
	def maxSubArraySum(arr: Array[Int], low: Int, high: Int): Int = {
		// Base Case: Only one element 
		if (low == high)
		{
			return arr(low);
		}
		// Find middle point 
		var middle: Int = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		var a: Int = maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		var b: Int = maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		var c: Int = maxSubArraySum(arr, middle + 1, high);
		return maxValue(maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	def findMaxSumSubarray(arr: Array[Int], n: Int): Unit = {
		// Display array elements
		printArray(arr, n);
		// Get max subarray sum
		var sum: Int = maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		print("\n Maximum sum subarray : " + sum + " \n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var task: MaximumSubarray = new MaximumSubarray();
		// 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
		task.findMaxSumSubarray(arr1, n);
		// Test B
		// Get the number of elements
		n = arr2.length;
		// [3, 1, 2, 8]
		// Result 14
		task.findMaxSumSubarray(arr2, n);
	}
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
import Foundation;
/*
    Swift 4 Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray
{
	// Display given array elements
	func printArray(_ arr: [Int], _ n: Int)
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" ", arr[i], terminator: "");
			i += 1;
		}
	}
	// Returns the maximum value of given two numbers
	func maxValue(_ a: Int, _ b: Int) -> Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	func maxSum(_ arr: [Int], _ low: Int, _ middle: Int, _ high: Int) -> Int
	{
		// Contain sum of left and right subarray
		var leftSum: Int = Int.min;
		var rightSum: Int = Int.min;
		var sum: Int = 0;
		var i: Int = middle;
		// Calculate left subarray sum
		while (i >= low)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
			i -= 1;
		}
		sum = 0;
		i = middle + 1;
		// Calculate right subarray sum
		while (i <= high)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
			i += 1;
		}
		return self.maxValue(
          self.maxValue(leftSum + rightSum, leftSum), 
          rightSum);
	}
	func maxSubArraySum(_ arr: [Int], _ low: Int, _ high: Int) -> Int
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		let middle: Int = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		let a: Int = self.maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		let b: Int = self.maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		let c: Int = self.maxSubArraySum(arr, middle + 1, high);
		return self.maxValue(self.maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	func findMaxSumSubarray(_ arr: [Int], _ n: Int)
	{
		// Display array elements
		self.printArray(arr, n);
		// Get max subarray sum
		let sum: Int = self.maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		print("\n Maximum sum subarray : ", sum ," ");
	}
}
func main()
{
	let task: MaximumSubarray = MaximumSubarray();
	// 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
	task.findMaxSumSubarray(arr1, n);
	// Test B
	// Get the number of elements
	n = arr2.count;
	// [3, 1, 2, 8]
	// Result 14
	task.findMaxSumSubarray(arr2, n);
}
main();

Output

  1  2  -5  1  2  -3  3  -2  8
 Maximum sum subarray :  9
  -5  1  2  -10  3  1  2  8  -2
 Maximum sum subarray :  14
/*
    Kotlin Program for
    Maximum sum subarray using divide and conquer
*/
class MaximumSubarray
{
	// Display given array elements
	fun printArray(arr: Array < Int > , n: Int): Unit
	{
		var i: Int = 0;
		while (i < n)
		{
			print(" " + arr[i]);
			i += 1;
		}
	}
	// Returns the maximum value of given two numbers
	fun maxValue(a: Int, b: Int): Int
	{
		if (a > b)
		{
			return a;
		}
		return b;
	}
	fun maxSum(arr: Array < Int > , low: Int, middle: Int, high: Int): Int
	{
		// Contain sum of left and right subarray
		var leftSum: Int = Int.MIN_VALUE;
		var rightSum: Int = Int.MIN_VALUE;
		var sum: Int = 0;
		var i: Int = middle;
		// Calculate left subarray sum
		while (i >= low)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > leftSum)
			{
				leftSum = sum;
			}
			i -= 1;
		}
		sum = 0;
		i = middle + 1;
		// Calculate right subarray sum
		while (i <= high)
		{
			// Current sum
			sum = sum + arr[i];
			if (sum > rightSum)
			{
				rightSum = sum;
			}
			i += 1;
		}
		return this.maxValue(
          this.maxValue(leftSum + rightSum, leftSum), 
          rightSum);
	}
	fun maxSubArraySum(arr: Array < Int > , low: Int, high: Int): Int
	{
		// Base Case: Only one element 
		if (low == high)
		{
			return arr[low];
		}
		// Find middle point 
		val middle: Int = (low + high) / 2;
		// Calculate the sum of left subarray from (low to middle).
		val a: Int = this.maxSubArraySum(arr, low, middle);
		// Calculate the sum of middle subarray from (middle to high).
		val b: Int = this.maxSum(arr, low, middle, high);
		// Calculate the sum of right subarray from (middle+1 to high).
		val c: Int = this.maxSubArraySum(arr, middle + 1, high);
		return this.maxValue(this.maxValue(a, b), c);
	}
	//  Handles the request of  finding max sum subarray
	fun findMaxSumSubarray(arr: Array < Int > , n: Int): Unit
	{
		// Display array elements
		this.printArray(arr, n);
		// Get max subarray sum
		val sum: Int = this.maxSubArraySum(arr, 0, n - 1);
		// Display calculated sum
		print("\n Maximum sum subarray : " + sum + " \n");
	}
}
fun main(args: Array < String > ): Unit
{
	val task: MaximumSubarray = MaximumSubarray();
	// 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
	task.findMaxSumSubarray(arr1, n);
	// Test B
	// Get the number of elements
	n = arr2.count();
	// [3, 1, 2, 8]
	// Result 14
	task.findMaxSumSubarray(arr2, n);
}

Output

 1 2 -5 1 2 -3 3 -2 8
 Maximum sum subarray : 9
 -5 1 2 -10 3 1 2 8 -2
 Maximum sum subarray : 14
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