数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序中重复连接后创建的数组中的最大子数组和
在这个问题中，我们得到一个大小为n的数组arr[]和一个整数k。我们的任务是创建一个程序，在重复连接后的数组中找到最大子数组和。
问题描述 − 我们将找到从重复连接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<<"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
这种方法很好，但可以使用更有效的模算术方法来解决问题。
模算术是指我们使用模运算符来获取方程的余数。
为了解决这个问题，我们将使用模算术而不是通过重复连接来创建数组。其余解决方案保持不变。
示例
演示我们解决方案工作的程序：
#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
更新于：2020年12月9日
144 次浏览
广告