在 C++ 中的数组 arr[] 中查找 abs(i – j) * min(arr[i], arr[j]) 的最大值

  • Z时代
  • 2024-01-10
  • 分类：综合

在这个问题中，我们给定了一个数组 arr[]，其中包含 N 个整数值。我们的任务是在数组 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(n 2 )。

该问题的有效解决方案是使用两个迭代器值，从另一个开始到数组末尾。对于迭代器的每个值，我们将找到所需的值并比较它们并将最大值存储在 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

以上是 在 C++ 中的数组 arr[] 中查找 abs(i – j) * min(arr[i], arr[j]) 的最大值 的全部内容， 来源链接： utcz.com/z/317416.html

回到顶部