算法设计：最大循环子数组总和

2021年4月17日17:55:43 发表评论 929 次浏览

本文概述

给定n个数字(+ ve和-ve), 它们排列成一个圆圈, 找出连续数字的最大和。

例子：

Input: a[] = {8, -8, 9, -9, 10, -11, 12}
Output: 22 (12 + 8 - 8 + 9 - 9 + 10)

Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1} 
Output:  23 (7 + 6 + 5 - 4 -1 + 10) 

Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1}
Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40)

方法1最大和可以有两种情况：

  • 情况1：排列有助于最大和的元素, 以使不存在任何包装。示例：{-10、2, -1、5}, {-2、4, -1、4, -1}。在这种情况下, Kadane的算法将产生结果。
  • 情况2：布置有助于最大和的元素, 使得存在包装。示例：{10, -12、11}, {12, -5、4, -8、11}。在这种情况下, 我们将换行更改为不换行。让我们看看如何。包装有贡献的元素意味着不包装无贡献的元素, 因此请找出无贡献元素的总和, 然后从总和中减去该总和。要找出无用的总和, 请反转每个元素的符号, 然后运行Kadane的算法。
    我们的阵列就像一个圆环, 我们必须消除最大连续负值, 这意味着倒置阵列中的最大连续正值。最后, 我们比较两种情况下获得的总和, 并返回两个总和的最大值。

以下是上述方法的C++/ C++, Java和Python实现。

C ++

//C++ program for maximum contiguous circular sum problem
#include <bits/stdc++.h>
using namespace std;
  
//Standard Kadane's algorithm to
//find maximum subarray sum
int kadane( int a[], int n);
  
//The function returns maximum
//circular contiguous sum in a[]
int maxCircularSum( int a[], int n)
{
     //Case 1: get the maximum sum using standard kadane'
     //s algorithm
     int max_kadane = kadane(a, n);
  
     //Case 2: Now find the maximum sum that includes
     //corner elements.
     int max_wrap = 0, i;
     for (i = 0; i <n; i++) {
         max_wrap += a[i]; //Calculate array-sum
         a[i] = -a[i]; //invert the array (change sign)
     }
  
     //max sum with corner elements will be:
     //array-sum - (-max subarray sum of inverted array)
     max_wrap = max_wrap + kadane(a, n);
  
     //The maximum circular sum will be maximum of two sums
     return (max_wrap> max_kadane) ? max_wrap : max_kadane;
}
  
//Standard Kadane's algorithm to find maximum subarray sum
//See https://www.lsbin.org/archives/576 for details
int kadane( int a[], int n)
{
     int max_so_far = 0, max_ending_here = 0;
     int i;
     for (i = 0; i <n; i++) {
         max_ending_here = max_ending_here + a[i];
         if (max_ending_here <0)
             max_ending_here = 0;
         if (max_so_far <max_ending_here)
             max_so_far = max_ending_here;
     }
     return max_so_far;
}
  
/* Driver program to test maxCircularSum() */
int main()
{
     int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
     int n = sizeof (a) /sizeof (a[0]);
     cout <<"Maximum circular sum is " <<maxCircularSum(a, n) <<endl;
     return 0;
}
  
//This is code is contributed by rathbhupendra

C

//C program for maximum contiguous circular sum problem
#include <stdio.h>
  
//Standard Kadane's algorithm to find maximum subarray
//sum
int kadane( int a[], int n);
  
//The function returns maximum circular contiguous sum
//in a[]
int maxCircularSum( int a[], int n)
{
     //Case 1: get the maximum sum using standard kadane'
     //s algorithm
     int max_kadane = kadane(a, n);
  
     //Case 2: Now find the maximum sum that includes
     //corner elements.
     int max_wrap = 0, i;
     for (i = 0; i <n; i++) {
         max_wrap += a[i]; //Calculate array-sum
         a[i] = -a[i]; //invert the array (change sign)
     }
  
     //max sum with corner elements will be:
     //array-sum - (-max subarray sum of inverted array)
     max_wrap = max_wrap + kadane(a, n);
  
     //The maximum circular sum will be maximum of two sums
     return (max_wrap> max_kadane) ? max_wrap : max_kadane;
}
  
//Standard Kadane's algorithm to find maximum subarray sum
//See https://www.lsbin.org/archives/576 for details
int kadane( int a[], int n)
{
     int max_so_far = 0, max_ending_here = 0;
     int i;
     for (i = 0; i <n; i++) {
         max_ending_here = max_ending_here + a[i];
         if (max_ending_here <0)
             max_ending_here = 0;
         if (max_so_far <max_ending_here)
             max_so_far = max_ending_here;
     }
     return max_so_far;
}
  
/* Driver program to test maxCircularSum() */
int main()
{
     int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
     int n = sizeof (a) /sizeof (a[0]);
     printf ( "Maximum circular sum is %dn" , maxCircularSum(a, n));
     return 0;
}

Java

//Java program for maximum contiguous circular sum problem
import java.io.*;
import java.util.*;
  
class MaxCircularSum {
     //The function returns maximum circular contiguous sum
     //in a[]
     static int maxCircularSum( int a[])
     {
         int n = a.length;
  
         //Case 1: get the maximum sum using standard kadane'
         //s algorithm
         int max_kadane = kadane(a);
  
         //Case 2: Now find the maximum sum that includes
         //corner elements.
         int max_wrap = 0 ;
         for ( int i = 0 ; i <n; i++) {
             max_wrap += a[i]; //Calculate array-sum
             a[i] = -a[i]; //invert the array (change sign)
         }
  
         //max sum with corner elements will be:
         //array-sum - (-max subarray sum of inverted array)
         max_wrap = max_wrap + kadane(a);
  
         //The maximum circular sum will be maximum of two sums
         return (max_wrap> max_kadane) ? max_wrap : max_kadane;
     }
  
     //Standard Kadane's algorithm to find maximum subarray sum
     //See https://www.lsbin.org/archives/576 for details
     static int kadane( int a[])
     {
         int n = a.length;
         int max_so_far = 0 , max_ending_here = 0 ;
         for ( int i = 0 ; i <n; i++) {
             max_ending_here = max_ending_here + a[i];
             if (max_ending_here <0 )
                 max_ending_here = 0 ;
             if (max_so_far <max_ending_here)
                 max_so_far = max_ending_here;
         }
         return max_so_far;
     }
  
     public static void main(String[] args)
     {
         int a[] = { 11 , 10 , - 20 , 5 , - 3 , - 5 , 8 , - 13 , 10 };
         System.out.println( "Maximum circular sum is " + maxCircularSum(a));
     }
} /* This code is contributed by Devesh Agrawal*/

python

# Python program for maximum contiguous circular sum problem
  
# Standard Kadane's algorithm to find maximum subarray sum
def kadane(a):
     n = len (a)
     max_so_far = 0
     max_ending_here = 0
     for i in range ( 0 , n):
         max_ending_here = max_ending_here + a[i]
         if (max_ending_here <0 ):
             max_ending_here = 0
         if (max_so_far <max_ending_here):
             max_so_far = max_ending_here
     return max_so_far
  
# The function returns maximum circular contiguous sum in
# a[]
def maxCircularSum(a):
  
     n = len (a)
  
     # Case 1: get the maximum sum using standard kadane's
     # algorithm
     max_kadane = kadane(a)
  
     # Case 2: Now find the maximum sum that includes corner
     # elements.
     max_wrap = 0
     for i in range ( 0 , n):
         max_wrap + = a[i]
         a[i] = - a[i]
  
     # Max sum with corner elements will be:
     # array-sum - (-max subarray sum of inverted array)
     max_wrap = max_wrap + kadane(a)
  
     # The maximum circular sum will be maximum of two sums
     if max_wrap> max_kadane:
         return max_wrap
     else :
         return max_kadane
  
# Driver function to test above function
a = [ 11 , 10 , - 20 , 5 , - 3 , - 5 , 8 , - 13 , 10 ]
print "Maximum circular sum is" , maxCircularSum(a)
  
# This code is contributed by Devesh Agrawal

C#

//C# program for maximum contiguous
//circular sum problem
using System;
  
class MaxCircularSum {
  
     //The function returns maximum circular
     //contiguous sum in a[]
     static int maxCircularSum( int [] a)
     {
         int n = a.Length;
  
         //Case 1: get the maximum sum using standard kadane'
         //s algorithm
         int max_kadane = kadane(a);
  
         //Case 2: Now find the maximum sum that includes
         //corner elements.
         int max_wrap = 0;
         for ( int i = 0; i <n; i++) {
             max_wrap += a[i]; //Calculate array-sum
             a[i] = -a[i]; //invert the array (change sign)
         }
  
         //max sum with corner elements will be:
         //array-sum - (-max subarray sum of inverted array)
         max_wrap = max_wrap + kadane(a);
  
         //The maximum circular sum will be maximum of two sums
         return (max_wrap> max_kadane) ? max_wrap : max_kadane;
     }
  
     //Standard Kadane's algorithm to find maximum subarray sum
     //See https://www.lsbin.org/archives/576 for details
     static int kadane( int [] a)
     {
         int n = a.Length;
         int max_so_far = 0, max_ending_here = 0;
         for ( int i = 0; i <n; i++) {
             max_ending_here = max_ending_here + a[i];
             if (max_ending_here <0)
                 max_ending_here = 0;
             if (max_so_far <max_ending_here)
                 max_so_far = max_ending_here;
         }
         return max_so_far;
     }
  
     //Driver code
     public static void Main()
     {
         int [] a = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
  
         Console.Write( "Maximum circular sum is " + maxCircularSum(a));
     }
}
  
/* This code is contributed by vt_m*/

PHP

<?php
  
//PHP program for maximum 
//contiguous circular sum problem 
  
//The function returns maximum 
//circular contiguous sum $a[] 
function maxCircularSum( $a , $n ) 
{ 
     //Case 1: get the maximum sum 
     //using standard kadane' s algorithm 
     $max_kadane = kadane( $a , $n ); 
      
     //Case 2: Now find the maximum  
     //sum that includes corner elements. 
     $max_wrap = 0;
     for ( $i = 0; $i <$n ; $i ++) 
     { 
             $max_wrap += $a [ $i ]; //Calculate array-sum 
             $a [ $i ] = - $a [ $i ]; //invert the array (change sign) 
     } 
      
     //max sum with corner elements will be: 
     //array-sum - (-max subarray sum of inverted array) 
     $max_wrap = $max_wrap + kadane( $a , $n ); 
      
     //The maximum circular sum will be maximum of two sums 
     return ( $max_wrap> $max_kadane )? $max_wrap : $max_kadane ; 
} 
  
//Standard Kadane's algorithm to 
//find maximum subarray sum 
//See https://www.lsbin.org/archives/576 for details 
function kadane( $a , $n ) 
{ 
     $max_so_far = 0;
     $max_ending_here = 0; 
     for ( $i = 0; $i <$n ; $i ++) 
     { 
         $max_ending_here = $max_ending_here + $a [ $i ]; 
         if ( $max_ending_here <0) 
             $max_ending_here = 0; 
         if ( $max_so_far <$max_ending_here ) 
             $max_so_far = $max_ending_here ; 
     } 
     return $max_so_far ; 
} 
  
     /* Driver code */
     $a = array (11, 10, -20, 5, -3, -5, 8, -13, 10); 
     $n = count ( $a );
     echo "Maximum circular sum is " . maxCircularSum( $a , $n ); 
  
//This code is contributed by rathbhupendra
?>

输出如下：

Maximum circular sum is 31

复杂度分析：

  • 时间复杂度：O(n), 其中n是输入数组中元素的数量。
    由于仅需要数组的线性遍历。
  • 辅助空间：O(1)。
    由于不需要额外的空间。

注意如果所有数字均为负数, 例如{-1, -2, -3}, 则上述算法无效。在这种情况下, 它返回0。在运行上述算法之前, 可以通过添加预检查以查看所有数字是否均为负来处理这种情况。

方法2

方法：

在这种方法中, 修改Kadane的算法以找到最小连续子数组和和最大连续子数组和, 然后检查max_value和从总和中减去min_value后剩下的值中的最大值。

算法

  1. 我们将计算给定数组的总和。
  2. 我们将变量curr_max, max_so_far, curr_min, min_so_far声明为数组的第一个值。
  3. 现在, 我们将使用Kadane的算法来找到最大子数组和和最小子数组和。
  4. 检查数组中的所有值：
    1. 如果min_so_far等于和, 即所有值均为负, 则返回max_so_far。
    2. 否则, 我们将计算max_so_far和(sum – min_so_far)的最大值并将其返回。

下面给出上述方法的C++实现。

C ++

//C++ program for maximum contiguous circular sum problem
#include <bits/stdc++.h>
using namespace std;
  
//The function returns maximum
//circular contiguous sum in a[]
int maxCircularSum( int a[], int n)
{
     //Corner Case
     if (n == 1)
         return a[0];
  
     //Initialize sum variable which store total sum of the array.
     int sum = 0;
     for ( int i = 0; i <n; i++) {
         sum += a[i];
     }
  
     //Initialize every variable with first value of array.
     int curr_max = a[0], max_so_far = a[0], curr_min = a[0], min_so_far = a[0];
  
     //Concept of Kadane's Algorithm
     for ( int i = 1; i <n; i++) {
         //Kadane's Algorithm to find Maximum subarray sum.
         curr_max = max(curr_max + a[i], a[i]);
         max_so_far = max(max_so_far, curr_max);
  
         //Kadane's Algorithm to find Minimum subarray sum.
         curr_min = min(curr_min + a[i], a[i]);
         min_so_far = min(min_so_far, curr_min);
     }
  
     if (min_so_far == sum)
         return max_so_far;
  
     //returning the maximum value
     return max(max_so_far, sum - min_so_far);
}
  
/* Driver program to test maxCircularSum() */
int main()
{
     int a[] = { 11, 10, -20, 5, -3, -5, 8, -13, 10 };
     int n = sizeof (a) /sizeof (a[0]);
     cout <<"Maximum circular sum is " <<maxCircularSum(a, n) <<endl;
     return 0;
}

输出如下：

Maximum circular sum is 31

复杂度分析：

  • 时间复杂度：O(n), 其中n是输入数组中元素的数量。
    由于仅需要数组的线性遍历。
  • 辅助空间：O(1)。
    由于不需要额外的空间。
木子山

发表评论

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