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

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

本文概述

你将获得一维数组, 其中可能同时包含正整数和负整数, 请找到具有最大和的连续数字子数组的和。

例如, 如果给定的数组为{-2, -5, 6, -2, -3, 1, 5, -6}, 则最大子数组总和为7(请参见突出显示的元素)。

天真的方法是要运行两个循环。外循环选择开始的元素, 内循环找到外循环选择的第一个元素的最大可能和, 并将此最大值与总体最大值进行比较。最后返回总体最大值。天真的方法的时间复杂度是O(n ^ 2)。

使用分而治之方法, 我们可以找到O(nLogn)时间中的最大子数组总和。以下是分而治之算法。

1)将给定数组分为两半

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

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

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

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

第2.a和2.b行是简单的递归调用。如何找到最大子数组和, 以使子数组越过中点？我们可以很容易地找到线性时间的相加和。这个想法很简单, 找到从中点开始并在中点左侧的某个点处结束的最大和, 然后找到从中点+ 1开始并以中点+ 1右边的和点结束的最大和。最后, 将两者合并然后返回。

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

时间复杂度：maxSubArraySum()是一种递归方法, 时间复杂度可以表示为以下递归关系。

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

上述递归类似于归并排序，可以用递归树法或主方法求解。它属于主方法的情形II，递归式的解为θ (nLogn)。

Kadane的算法对于这个问题需要O(n)时间。因此, Kadane的算法比分而治之方法要好, 但是这个问题可以看作是展示分而治之功效的一个很好的例子。上面将数组分为两半的简单方法将时间复杂度从O(n ^ 2)减少到O(nLogn)。

参考文献：

Clifford Stein, Thomas H.Cormen, Charles E.Leiserson, Ronald L.

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: