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