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 : 14package 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 : 14import 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 : 14import 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 : 14Explanation 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.
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