C ++中最大循环子数组总和

给我们一个数组，任务是形成子数组，使得子数组的总和以循环的方式产生最大值。

输入− int arr [] = {1,2,8,4,3,0,7}

输出-最大圆形子数组总和为-22

解释-我们得到了一个包含{1,2,8,4,3,0,7}的数组，它的子数组最大和为7 + 1 + 2+ 8 + 4是22。

输入− int arr [] = {2，5，-1，6，9，4，-5}

输出-最大圆形子数组总和为-25

解释-我们得到一个包含{2，5，-1，6，9，4，-5}的数组，其最大和为4 + 2 + 5-1-6 + 9的子数组为25。

以下程序中使用的方法如下

• 输入包含正值和负值的整数元素数组。

• 计算数组的大小。

• 将数组和大小传递给函数以进行进一步处理。

• 创建一个临时变量total并将其设置为0

• 从i到0开始循环直到数组大小

• 在循环内，用total + arr [i]设置total

• 设置温度= arr [0]，temp_2 = arr [0]，temp_3 = arr [0]，temp_4 = arr [0]

• 从i到1开始循环，直到数组大小

• 在循环内设置temp = max（temp + arr [i]，arr [i]），temp_2 = max(temp_2,temp)，temp_3 = min（temp_3 + arr [i]，arr [i]），temp_4 = min (temp_4,temp_3)

• 检查IF大小== 1，然后返回arr [0]

• 检查IF temp_4 == total，然后返回temp_2

• 设置max_sum = max(temp_3,total-temp_4)

• 返回max_sum

• 打印结果。

示例

#include <bits/stdc++.h>
using namespace std;
int maximum(int arr[], int size){
   int total = 0;
   for (int i = 0; i < size; i++){
      total += arr[i];
   }
   int temp = arr[0];
   int temp_2 = arr[0];
   int temp_3 = arr[0];
   int temp_4 = arr[0];
   for (int i = 1; i < size; i++){
      temp = max(temp + arr[i], arr[i]);
      temp_2 = max(temp_2, temp);
      temp_3 = min(temp_3 + arr[i], arr[i]);
      temp_4 = min(temp_4, temp_3);
   }
   if (size == 1){
      return arr[0];
   }
   if (temp_4 == total){
      return temp_2;
   }
   int max_sum = max(temp_3, total - temp_4);
   return max_sum;
}
int main(){
   int arr[] = { 2, 5, -1, 6, 9, 4, -5 };
   int size = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximum circular subarray sum is: "<<maximum(arr, size) << endl;
   return 0;
}

输出结果

如果我们运行上面的代码，它将生成以下输出-

Maximum circular subarray sum is: 25