数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++中给定大小的两个不相交子数组的最大和
在这个问题中，我们得到一个正整数数组和一个数字k。我们的任务是创建一个程序，找到给定大小(k)的两个不相交子数组的最大和。
所以，基本上我们需要打印两个不相交（不同的）子数组，它们具有最大和并且大小为k。
让我们举个例子来理解这个问题：
输入 −
array = {7, 1, 6, 9, 2} , k = 2输出 −
{7, 1} , {6, 9}解释 −
all subarrays of size 2.
{7, 1} : sum = 7+1 = 8
{1, 6} : sum = 1+6 = 7
{6, 9} : sum = 6+9 = 15
{9, 2} : sum = 9+2 = 11
Two non-overlapping subarrays with max sums are {7,1} and {6,9}为了解决这个问题，一个简单的方案是找到所有子数组及其和，然后检查两个不相交的最大子数组。
一个有效的解决方法是使用前缀和数组，它存储直到数组元素的所有元素的和。然后检查k个元素的子数组以找到具有最大和的子数组。
示例
显示我们解决方案实现的程序：
#include <bits/stdc++.h>
using namespace std;
int findSubArraySum(int sum[], int i, int j){
if (i == 0)
return sum[j];
else
return (sum[j] - sum[i - 1]);
}
void maxSubarray(int arr[],int N, int K){
int prefixsum[N];
prefixsum[0] = arr[0];
for (int i = 1; i < N; i++)
prefixsum[i] = prefixsum[i - 1] + arr[i];
pair<int, int> resIndex = make_pair(N - 2 * K, N - K);
int maxSubarraySum = findSubArraySum(prefixsum, N - 2 * K, N - K - 1) + findSubArraySum(prefixsum, N - K, N - 1);
pair<int, int> secondSubarrayMax = make_pair(N - K, findSubArraySum(prefixsum, N - K, N - 1));
for (int i = N - 2 * K - 1; i >= 0; i--){
int cur = findSubArraySum(prefixsum, i + K, i + 2 * K - 1);
if (cur >= secondSubarrayMax.second)
secondSubarrayMax = make_pair(i + K, cur);
cur = findSubArraySum(prefixsum, i, i + K - 1) + secondSubarrayMax.second;
if (cur >= maxSubarraySum){
maxSubarraySum = cur;
resIndex = make_pair(i, secondSubarrayMax.first);
}
}
cout<<"{ ";
for (int i = resIndex.first; i <resIndex.first + K; i++)
cout<<arr[i]<<" ";
cout<<"}"<<endl<<"{ ";
for (int i = resIndex.second; i < resIndex.second + K; i++)
cout<<arr[i]<<" ";
cout<<"}"<<endl;
}
int main(){
int arr[] = {2, 5, 1, 2, 7, 3, 0};
int N = sizeof(arr) / sizeof(int);
int K = 2;
cout<<"Two non-overlapping subarrays with maximum sum are \n";
maxSubarray(arr, N, K);
return 0;
}输出
Two non-overlapping subarrays with maximum sum are
{ 2 5 }
{ 7 3 }
更新于: 2020年6月3日
142 次查看
广告