数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法学研究在C++中查找数组arr[]中abs(i – j) * min(arr[i], arr[j])的最大值
在这个问题中，我们得到一个包含N个整数值的数组arr[]。我们的任务是在数组arr[]中找到abs(i – j) * min(arr[i], arr[j])的最大值。
问题描述 - 我们需要找到两个元素的最小值与它们索引之间绝对差的乘积最大值。即对于两个值i和j，我们需要最大化abs(i - j) * min(arr[i] , arr[j])。
输入
arr[] = {5, 7, 3, 6, 4}输出
16
解释
The maximum value is 16, between index 0 and 4 => abs(0 - 4)*min(arr[0], arr[4]) => 4*min(5, 4) => 4*4 = 16
解决方案
解决这个问题的一个简单方法是使用嵌套循环。我们将使用两个循环计算每对i和j的值。然后返回找到的所有值中的最大值。
这种方法很好，但时间复杂度为O(n2)。
解决这个问题的一个有效方法是使用两个迭代器值，一个从数组的开头，另一个从数组的结尾。对于迭代器的每个值，我们将找到所需的值，进行比较并将最大值存储在maxVal变量中。我们将这样做，直到两个迭代器交叉，最后返回maxVal。
程序说明了我们解决方案的工作原理：
示例
#include<iostream>
using namespace std;
int calcMaxProdValue(int arr[], int n) {
int maxVal = -100;
int currentVal;
int start = 0, end = n-1;
while (start < end) {
if (arr[start] < arr[end]) {
currentVal = arr[start]*(end-start);
start++;
}
else {
currentVal = arr[end]*(end-start);
end--;
}
maxVal = max(maxVal, currentVal);
}
return maxVal;
}
int main(){
int arr[] = {5, 7, 3, 6, 4};
int n = sizeof(arr)/sizeof(arr[0]);
cout<<"The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is "<<calcMaxProdValue(arr,n);
return 0;
}输出
The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16
更新于：2021年3月12日
323 次浏览
广告