ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ที่ยืนยันค่าจำนวนเต็ม N ค่า งานของเราคือค้นหาค่าสูงสุดของ abs(i – j) * min(arr[i], arr[j]) ใน arrayarr[]
คำอธิบายปัญหา − เราจำเป็นต้องค้นหามูลค่าผลิตภัณฑ์สูงสุดของค่าต่ำสุดของสององค์ประกอบและความแตกต่างสัมบูรณ์ระหว่างดัชนีของพวกมัน นั่นคือ สำหรับสองค่า 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
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือการใช้การวนซ้ำซ้อน เราจะใช้ twoloop และคำนวณค่าสำหรับแต่ละคู่ของ i และ j แล้วคืนค่าสูงสุดของค่าทั้งหมดที่พบ
วิธีนี้เป็นวิธีที่ดีแต่มีเวลาที่ซับซ้อนของคำสั่ง O(n 2 )
วิธีแก้ปัญหาที่มีประสิทธิภาพคือการใช้ค่าตัววนซ้ำสองค่า จากจุดเริ่มต้นอีกค่าหนึ่งจากส่วนท้ายของอาร์เรย์ สำหรับแต่ละค่าของ iterators เราจะค้นหาค่าที่ต้องการและเปรียบเทียบและเก็บตัวแปร inmaxVal สูงสุด เราจะทำเช่นนี้จนกว่าตัววนซ้ำทั้งสองจะข้ามกันและในตอนท้ายจะคืนค่า 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
