C++程序 最大循环子数组和

C++程序 最大循环子数组和

给定n个数字(正负都有),排成一个圆圈,找到连续数字的最大总和。

例子:

输入: a[] = {8, -8, 9, -9, 10, -11, 12}
输出: 22 (12 + 8 – 8 + 9 – 9 + 10)

输入: a[] = {10, -3, -4, 7, 6, 5, -4, -1}
输出: 23 (7 + 6 + 5 – 4 -1 + 10)

输入: a[] = {-1, 40, -14, 7, 6, 5, -4, -1}
输出: 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++程序
#include <bits/stdc++.h>
using namespace std;
  
//找到最大子数组和的标准Kadane算法
int kadane(int a[], int n);
  
// 该函数返回a []中最大的循环连续总和
int maxCircularSum(int a[], int n)
{
    // 情况1:使用标准的kadane'找到最大和
    int max_kadane = kadane(a, n);
     //如果使用标准kadane'的最大总和小于0
    if(max_kadane < 0)
      return max_kadane;
  
    // 情况2:现在找到包括角元素的最大和。
    int max_wrap = 0, i;
    for (i = 0; i < n; i++) {
        max_wrap += a[i]; // 计算数组总和
        a[i] = -a[i]; // 反转数组(改变符号)
    }
  
    // 带角元素的最大总和将是:
    //数组总和-(反转数组的最大子数组总和)
    max_wrap = max_wrap + kadane(a, n);
  
    // 最大的循环总和将是两个总和中的最大值
    return (max_wrap > max_kadane) ? max_wrap : max_kadane;
}
  
//找到最大子数组和的标准Kadane算法
//有关详细信息,请参见 https://www.geeksforgeeks.org/archives/576
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_so_far < max_ending_here)
            max_so_far = max_ending_here;
          if (max_ending_here < 0)
              max_ending_here = 0;
    }
    return max_so_far;
}
  
/*主程序,用于测试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;
}
  
//此代码由rathbhupendra贡献```  

输出:

最大循环总和为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等于sum,即所有值都为负数,则返回max_so_far。
2. 否则,我们将计算max_so_far和(sum-min_so_far)的最大值,并返回它。

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

// 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)。 因为不需要额外的空间。

Python教程

Java教程

Web教程

数据库教程

图形图像教程

大数据教程

开发工具教程

计算机教程

C++ 示例