在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
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短