資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中兩個陣列的最大和路徑
問題陳述
給定兩個排序陣列，這些陣列可能有一些公共元素。找到從任何陣列的開頭到兩個陣列中任何一個數組的末尾的最大和路徑的總和。我們只能在公共元素處從一個數組切換到另一個數組。請注意，公共元素不必位於相同的索引處。
預期時間複雜度為 O(m+n)，其中 m 是 arr1[] 中元素的數量，n 是 arrs2[] 中元素的數量
示例
If given input is then output is 35
arr1[] = {2, 3, 7, 10, 12}
ar2[] = {1, 5, 7, 8}
(1 + 5 + 7 + 10 + 12) = 351. 我們從 arr2 的第一個元素 1 開始，然後移動到 5，然後移動到 7。
從 7 開始，我們切換到 ar1（7 是公共的）並遍歷 10 和 12。
演算法
這個想法是做一些類似於歸併排序的合併過程的事情。我們需要計算兩個陣列中所有公共點之間元素的總和。每當我們看到一個公共點時，我們比較這兩個總和並將兩個總和中的最大值新增到結果中。
將結果初始化為 0。還將兩個變數 sum1 和 sum2 初始化為 0。這裡 sum1 和 sum2 用於分別儲存 arr1[] 和 arr2[] 中元素的總和。這些總和位於兩個公共點之間
現在執行一個迴圈來遍歷兩個陣列的元素。在遍歷時比較 arr1[] 和 arr2[] 的當前元素
如果 arr1[] 的當前元素小於 arr2[] 的當前元素，則更新 sum1，否則如果 arr2[] 的當前元素較小，則更新 sum
如果 arr1[] 和 arr2[] 的當前元素相同，則取 sum1 和 sum2 中的最大值並將其新增到結果中。還將公共元素新增到結果中
示例
#include <bits/stdc++.h>
using namespace std;
int max(int x, int y){
return (x > y)? x : y;
}
int maxPathSum(int *arr1, int *arr2, int m, int n){
int i = 0, j = 0;
int result = 0, sum1 = 0, sum2 = 0;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
sum1 += arr1[i++];
} else if (arr1[i] > arr2[j]) {
sum2 += arr2[j++];
} else {
result += max(sum1, sum2);
sum1 = 0, sum2 = 0;
while (i < m && j < n && arr1[i] == arr2[j]) {
result = result + arr1[i++];
j++;
}
}
}
while (i < m) {
sum1 += arr1[i++];
}
while (j < n) {
sum2 += arr2[j++];
}
result += max(sum1, sum2);
return result;
}
int main(){
int arr1[] = {2, 3, 7, 10, 12};
int arr2[] = {1, 5, 7, 8};
int m = sizeof(arr1)/sizeof(arr1[0]);
int n = sizeof(arr2)/sizeof(arr2[0]);
cout << "Maximum sum path = " << maxPathSum(arr1, arr2, m, n) << endl;
return 0;
}輸出
當您編譯並執行上述程式時。它生成以下輸出 -
Maximum sum path = 35
更新於: 2020-01-30
529 次檢視
廣告