資料結構
網路
關係資料庫管理系統(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 次檢視
廣告