# 算法题：使用分治算法的最大子数组总和

2021年4月17日18:18:54 发表评论 940 次浏览

## 本文概述

1)将给定数组分为两半

2)返回以下三个的最大值

…。a)左半部分的最大子数组总和(进行递归调用)

…。b)右半部分的最大子数组总和(进行递归调用)

…。c)最大子数组总和, 以使子数组越过中点

## C++

``````//A Divide and Conquer based program for maximum subarray sum problem
#include <stdio.h>
#include <limits.h>

//A utility funtion to find maximum of two integers
int max( int a, int b) { return (a> b)? a : b; }

//A utility funtion to find maximum of three integers
int max( int a, int b, int c) { return max(max(a, b), c); }

//Find the maximum possible sum in arr[] auch that arr[m] is part of it
int maxCrossingSum( int arr[], int l, int m, int h)
{
//Include elements on left of mid.
int sum = 0;
int left_sum = INT_MIN;
for ( int i = m; i>= l; i--)
{
sum = sum + arr[i];
if (sum> left_sum)
left_sum = sum;
}

//Include elements on right of mid
sum = 0;
int right_sum = INT_MIN;
for ( int i = m+1; i <= h; i++)
{
sum = sum + arr[i];
if (sum> right_sum)
right_sum = sum;
}

//Return sum of elements on left and right of mid
//returning only left_sum + right_sum will fail for [-2, 1]
return max(left_sum + right_sum, left_sum, right_sum);
}

//Returns sum of maxium sum subarray in aa[l..h]
int maxSubArraySum( int arr[], int l, int h)
{
//Base Case: Only one element
if (l == h)
return arr[l];

//Find middle point
int m = (l + h)/2;

/* Return maximum of following three possible cases
a) Maximum subarray sum in left half
b) Maximum subarray sum in right half
c) Maximum subarray sum such that the subarray crosses the midpoint */
return max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h), maxCrossingSum(arr, l, m, h));
}

/*Driver program to test maxSubArraySum*/
int main()
{
int arr[] = {2, 3, 4, 5, 7};
int n = sizeof (arr)/sizeof (arr[0]);
int max_sum = maxSubArraySum(arr, 0, n-1);
printf ( "Maximum contiguous sum is %dn" , max_sum);
getchar ();
return 0;
}``````

## Java

``````//A Divide and Conquer based Java
//program for maximum subarray sum
//problem
import java.util.*;

class GFG {

//Find the maximum possible sum in arr[]
//such that arr[m] is part of it
static int maxCrossingSum( int arr[], int l, int m, int h)
{
//Include elements on left of mid.
int sum = 0 ;
int left_sum = Integer.MIN_VALUE;
for ( int i = m; i>= l; i--)
{
sum = sum + arr[i];
if (sum> left_sum)
left_sum = sum;
}

//Include elements on right of mid
sum = 0 ;
int right_sum = Integer.MIN_VALUE;
for ( int i = m + 1 ; i <= h; i++)
{
sum = sum + arr[i];
if (sum> right_sum)
right_sum = sum;
}

//Return sum of elements on left
//and right of mid
//returning only left_sum + right_sum will fail for [-2, 1]
return Math.max(left_sum + right_sum, Math.max(left_sum, right_sum));
}

//Returns sum of maxium sum subarray
//in aa[l..h]
static int maxSubArraySum( int arr[], int l, int h)
{
//Base Case: Only one element
if (l == h)
return arr[l];

//Find middle point
int m = (l + h)/2 ;

/* Return maximum of following three
possible cases:
a) Maximum subarray sum in left half
b) Maximum subarray sum in right half
c) Maximum subarray sum such that the
subarray crosses the midpoint */
return Math.max(Math.max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+ 1 , h)), maxCrossingSum(arr, l, m, h));
}

/* Driver program to test maxSubArraySum */
public static void main(String[] args)
{
int arr[] = { 2 , 3 , 4 , 5 , 7 };
int n = arr.length;
int max_sum = maxSubArraySum(arr, 0 , n- 1 );

System.out.println( "Maximum contiguous sum is " +
max_sum);
}
}
//This code is contributed by Prerna Saini``````

## Python3

``````# A Divide and Conquer based program
# for maximum subarray sum problem

# Find the maximum possible sum in
# arr[] auch that arr[m] is part of it
def maxCrossingSum(arr, l, m, h) :

# Include elements on left of mid.
sm = 0 ; left_sum = - 10000

for i in range (m, l - 1 , - 1 ) :
sm = sm + arr[i]

if (sm> left_sum) :
left_sum = sm

# Include elements on right of mid
sm = 0 ; right_sum = - 1000
for i in range (m + 1 , h + 1 ) :
sm = sm + arr[i]

if (sm> right_sum) :
right_sum = sm

# Return sum of elements on left and right of mid
# returning only left_sum + right_sum will fail for [-2, 1]
return max (left_sum + right_sum, left_sum, right_sum)

# Returns sum of maxium sum subarray in aa[l..h]
def maxSubArraySum(arr, l, h) :

# Base Case: Only one element
if (l = = h) :
return arr[l]

# Find middle point
m = (l + h) //2

# Return maximum of following three possible cases
# a) Maximum subarray sum in left half
# b) Maximum subarray sum in right half
# c) Maximum subarray sum such that the
#     subarray crosses the midpoint
return max (maxSubArraySum(arr, l, m), maxSubArraySum(arr, m + 1 , h), maxCrossingSum(arr, l, m, h))

# Driver Code
arr = [ 2 , 3 , 4 , 5 , 7 ]
n = len (arr)

max_sum = maxSubArraySum(arr, 0 , n - 1 )
print ( "Maximum contiguous sum is " , max_sum)

# This code is contributed by Nikita Tiwari.``````

## C#

``````//A Divide and Conquer based C#
//program for maximum subarray sum
//problem
using System;

class GFG {

//Find the maximum possible sum in arr[]
//such that arr[m] is part of it
static int maxCrossingSum( int []arr, int l, int m, int h)
{
//Include elements on left of mid.
int sum = 0;
int left_sum = int .MinValue;
for ( int i = m; i>= l; i--)
{
sum = sum + arr[i];
if (sum> left_sum)
left_sum = sum;
}

//Include elements on right of mid
sum = 0;
int right_sum = int .MinValue;;
for ( int i = m + 1; i <= h; i++)
{
sum = sum + arr[i];
if (sum> right_sum)
right_sum = sum;
}

//Return sum of elements on left
//and right of mid
//returning only left_sum + right_sum will fail for [-2, 1]
return Math.Max(left_sum + right_sum, Math.Max(left_sum, right_sum));
}

//Returns sum of maxium sum subarray
//in aa[l..h]
static int maxSubArraySum( int []arr, int l, int h)
{

//Base Case: Only one element
if (l == h)
return arr[l];

//Find middle point
int m = (l + h)/2;

/* Return maximum of following three
possible cases:
a) Maximum subarray sum in left half
b) Maximum subarray sum in right half
c) Maximum subarray sum such that the
subarray crosses the midpoint */
return Math.Max(Math.Max(maxSubArraySum(arr, l, m), maxSubArraySum(arr, m+1, h)), maxCrossingSum(arr, l, m, h));
}

/* Driver program to test maxSubArraySum */
public static void Main()
{
int []arr = {2, 3, 4, 5, 7};
int n = arr.Length;
int max_sum = maxSubArraySum(arr, 0, n-1);

Console.Write( "Maximum contiguous sum is " +
max_sum);
}
}

//This code is contributed by vt_m.``````

## PHP

``````<?php
//A Divide and Conquer based program
//for maximum subarray sum problem

//Find the maximum possible sum in arr[]
//such that arr[m] is part of it
function maxCrossingSum(& \$arr , \$l , \$m , \$h )
{
//Include elements on left of mid.
\$sum = 0;
\$left_sum = PHP_INT_MIN;
for ( \$i = \$m ; \$i>= \$l ; \$i --)
{
\$sum = \$sum + \$arr [ \$i ];
if ( \$sum> \$left_sum )
\$left_sum = \$sum ;
}

//Include elements on right of mid
\$sum = 0;
\$right_sum = PHP_INT_MIN;
for ( \$i = \$m + 1; \$i <= \$h ; \$i ++)
{
\$sum = \$sum + \$arr [ \$i ];
if ( \$sum> \$right_sum )
\$right_sum = \$sum ;
}

//Return sum of elements on left
//and right of mid
//returning only left_sum + right_sum will fail for [-2, 1]
return max( \$left_sum + \$right_sum , \$left_sum , \$right_sum );
}

//Returns sum of maxium sum
//subarray in aa[l..h]
function maxSubArraySum(& \$arr , \$l , \$h )
{
//Base Case: Only one element
if ( \$l == \$h )
return \$arr [ \$l ];

//Find middle point
\$m = intval (( \$l + \$h ) /2);

/* Return maximum of following three possible cases
a) Maximum subarray sum in left half
b) Maximum subarray sum in right half
c) Maximum subarray sum such that the
subarray crosses the midpoint */
return max(maxSubArraySum( \$arr , \$l , \$m ), maxSubArraySum( \$arr , \$m + 1, \$h ), maxCrossingSum( \$arr , \$l , \$m , \$h ));
}

//Driver Code
\$arr = array (2, 3, 4, 5, 7);
\$n = count ( \$arr );
\$max_sum = maxSubArraySum( \$arr , 0, \$n - 1);
echo "Maximum contiguous sum is " . \$max_sum ;

//This code is contributed by rathbhupendra, Aadil
?>``````

``Maximum contiguous sum is 21``

T(n)= 2T(n/2)+Θ(n)