数据结构
网络
关系型数据库管理系统
操作系统
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 次查看
广告