Posted on by Kalkicode
Code Divide And Conquer

Maximum sum subarray using divide and conquer

In this article, we will discuss the concept of finding the maximum sum subarray using the divide and conquer approach. The problem statement involves finding a contiguous subarray within a given array that has the largest sum. We will explain the problem, provide the pseudocode algorithm with explanations, and analyze the time complexity of the code. Let's dive in!

Problem Statement

Given an array of integers, the task is to find the maximum sum that can be obtained by summing the elements of a subarray. The subarray must consist of consecutive elements from the original array. For example, in the array [1, 2, -5, 1, 2, -3, 3, -2, 8], the maximum sum subarray is [1, 2, -3, 3, -2, 8] with a sum of 9.

Pseudocode Algorithm


function maxSubArraySum(arr, low, high):
	// Base Case: Only one element
	if low == high:
		return arr[low]

	// Find middle point
	middle = (low + high) / 2

	// Calculate the sum of the left subarray from (low to middle)
	a = maxSubArraySum(arr, low, middle)

	// Calculate the sum of the middle subarray from (middle to high)
	b = maxSum(arr, low, middle, high)

	// Calculate the sum of the right subarray from (middle+1 to high)
	c = maxSubArraySum(arr, middle + 1, high)

	return maxValue(maxValue(a, b), c)

function maxSum(arr, low, middle, high):
	// Initialize sum variables
	leftSum = INT_MIN
	rightSum = INT_MIN
	sum = 0

	// Calculate the sum of the left subarray
	for i from middle to low:
		sum += arr[i]
		if sum > leftSum:
			leftSum = sum

	sum = 0

	// Calculate the sum of the right subarray
	for i from middle + 1 to high:
		sum += arr[i]
		if sum > rightSum:
			rightSum = sum

	return maxValue(maxValue(leftSum + rightSum, leftSum), rightSum)

function findMaxSumSubarray(arr, n):
	printArray(arr, n)
	sum = maxSubArraySum(arr, 0, n - 1)
	print("Maximum sum subarray: " + sum)

The algorithm uses the divide and conquer strategy to find the maximum sum subarray. It splits the problem into smaller subproblems until it reaches the base case of a single element. Then, it combines the results of the subproblems to find the maximum sum subarray. The maxSubArraySum function recursively divides the array into two halves and calculates the maximum sum subarray in each half. The maxSum function calculates the maximum sum subarray that crosses the middle of the array. The findMaxSumSubarray function calls the other functions and displays the output.

Code Solution

/*
    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

Explanation and Result

Let's consider two test cases to demonstrate the algorithm's functionality.

Test Case A


// Given array elements
int arr1[] = {1, 2, -5, 1, 2, -3, 3, -2, 8};

// Get the number of elements
int n = sizeof(arr1) / sizeof(arr1[0]);

// [1, 2, -3, 3, -2, 8]
// Result: 9

findMaxSumSubarray(arr1, n);

The input array is [1, 2, -5, 1, 2, -3, 3, -2, 8]. The maximum sum subarray is [1, 2, -3, 3, -2, 8] with a sum of 9. The program displays the array elements and the maximum sum subarray as the output.

Test Case B


// Given array elements
int arr2[] = {-5, 1, 2, -10, 3, 1, 2, 8, -2};

// Get the number of elements
n = sizeof(arr2) / sizeof(arr2[0]);

// [3, 1, 2, 8]
// Result: 14

findMaxSumSubarray(arr2, n);

The input array is [-5, 1, 2, -10, 3, 1, 2, 8, -2]. The maximum sum subarray is [3, 1, 2, 8] with a sum of 14. The program displays the array elements and the maximum sum subarray as the output.

The time complexity of the algorithm is O(n log n) since each level of recursion splits the array into two halves, and there are a total of log n levels. At each level, the maxSum function iterates over a subarray of size n, resulting in an overall time complexity of O(n log n).

The divide and conquer approach provides an efficient solution to find the maximum sum subarray. By dividing the problem into smaller subproblems and combining the results, we can obtain the desired output in an optimized manner.

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