資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告