在 C++ 中的数组 arr[] 中查找 abs(i – j) * min(arr[i], arr[j]) 的最大值!
在这个问题中,我们给定了一个数组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(n2)。
该问题的有效解决方案是使用两个迭代器值,从另一个开始到数组末尾。对于迭代器的每个值,我们将找到所需的值并比较它们并将最大值存储在maxVal变量中。我们将这样做直到两个迭代器相互交叉并最终返回maxVal。
程序来说明我们的解决方案的工作,
示例
#includeusing 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 "< 输出结果 The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16