在C ++程序中反复连接后创建的数组中的最大子数组总和

在这个问题中，我们得到了大小为n且整数为k的数组arr []。我们的任务是创建一个程序，在重复连接后创建的数组中查找最大子数组和。

问题描述-我们将发现子数组的最大和是从重复arr，k次后创建的数组中获取的。

示例

让我们以一个例子来理解这个问题。

输入项

arr[] = {−9, −5, 14, 6} k = 2

输出结果

26

说明

New array after repeating : {−9, −5, 14, 6, −9, −5, 14, 6}
Subarray with maximum sum = {14, 6, −9, −5, 14, 6}
Sum = 26

解决方法

一个简单的解决方案是创建一个新的数组，该数组将在将arr []（k时间）串联后形成，然后找到具有最大总和的子数组。为此，最好的方法是使用Kadane算法。

示例

该程序说明了我们解决方案的工作原理，

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
   int newArr[2*n];
   for(int i = 0; i < k*n; i++)
   newArr[i] = arr[i%n];
   int maxSum = −1000, sum = 0;
   for (int i = 0; i < k*n; i++) {
      sum = sum + newArr[i];
      if (maxSum < sum)
         maxSum = sum;
      if (sum < 0)
         sum = 0;
   }
   return maxSum;
}
int main(){
   int arr[] = { −9, −5, 14, 6 };
   int k = 2;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"重复串联后创建的数组中的最大子数组总和为 "<<calcMaxSubArraySum(arr, n, k);
   return 0;
}

输出结果

The maximum subarray sum in an array created after repeated
concatenation is 26

这种方法很好，但是使用模块化算法可以解决问题，并且效率更高。

模数运算是当我们使用模运算符来获取方程的余数时。

为了解决该问题，我们将使用模块化算法，而不是通过重复级联来创建数组。其余解决方案保持不变。

示例

程序来说明我们的解决方案的工作原理，

#include <iostream>
using namespace std;
int calcMaxSubArraySum(int arr[], int n, int k){
   int maxSum = −1000, sum = 0;
   for (int i = 0; i < k*n; i++) {
      sum = sum + arr[i%n];
      if (maxSum < sum)
         maxSum = sum;
      if (sum < 0)
         sum = 0;
   }
   return maxSum;
}
int main(){
   int arr[] = { −9, −5, 14, 6 };
   int k = 2;
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum subarray sum in an array created after
   repeated concatenation is "<<calcMaxSubArraySum(arr, n, k);
   return 0;
}

输出结果

The maximum subarray sum in an array created after repeated
concatenation is 26