Trong bài toán này, chúng ta được cung cấp một mảng arr [] chứa N giá trị nguyên. Nhiệm vụ là Tìm giá trị lớn nhất của abs (i - j) * min (arr [i], arr [j]) trong arrayarr [].
Mô tả sự cố - chúng ta cần tìm giá trị tích lớn nhất của giá trị nhỏ nhất của hai phần tử và sự khác biệt tuyệt đối giữa các chỉ số của chúng. tức là đối với hai giá trị i và j, chúng ta cần tối đa hóa, abs (i - j) * min (arr [i], arr [j]).
Đầu vào
arr[] = {5, 7, 3, 6, 4} Đầu ra
16
Giải thích
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
Cách tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là sử dụng các vòng lặp lồng nhau. chúng tôi sẽ lấy twoloops và tính toán giá trị cho từng cặp i và j. Và sau đó trả về chúng tối đa của tất cả các giá trị được tìm thấy.
Cách tiếp cận này tốt nhưng phức tạp về thời gian theo thứ tự O (n 2 ).
Một giải pháp hiệu quả cho vấn đề là sử dụng hai giá trị của trình lặp, từ đầu của giá trị kia từ cuối mảng. Đối với mỗi giá trị của các trình vòng lặp, chúng tôi sẽ tìm giá trị cần thiết và so sánh chúng và lưu trữ biến inmaxVal tối đa. Chúng tôi sẽ làm điều này cho đến khi cả hai trình vòng lặp giao nhau và cuối cùng trả về maxVal.
Chương trình minh họa hoạt động của giải pháp của chúng tôi,
Ví dụ
#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;
} Đầu ra
The maximum value of abs(i – j) * min(arr[i], arr[j]) in an array is 16