Tìm max của abs(i-j)*min(arr[i],arr[j]) trong mảng C++

Mô tả vấn đề

Cho mảng arr[] N số nguyên. Tìm giá trị lớn nhất của biểu thức abs(i - j) * min(arr[i], arr[j]) với mọi cặp chỉ số i, j.

Ví dụ minh họa

Đầu vào:

arr[] = {5, 7, 3, 6, 4}

Đầu ra:

16

Giải thích:

Max tại cặp (0,4): abs(0-4)*min(5,4) = 4*4 = 16

Phương pháp giải quyết

Cách đơn giản (O(n²)): Hai vòng lặp lồng nhau kiểm tra mọi cặp.

Cách tối ưu (O(n) - Hai con trỏ): Khởi tạo start=0, end=n-1. Tại mỗi bước:

• Tính giá trị hiện tại = min(arr[start], arr[end]) * (end - start)
• Cập nhật maxVal
• Di chuyển con trỏ trỏ đến giá trị nhỏ hơn (vì giá trị lớn hơn có thể tạo tích lớn hơn khi khoảng cách giảm dần)

Chương trình minh họa

#include <iostream>
using namespace std;

int calcMaxProdValue(int arr[], int n) {
    int maxVal = -100;
    int start = 0, end = n - 1;
    while (start < end) {
        int currentVal;
        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 << "Giá trị lớn nhất của abs(i-j)*min(arr[i],arr[j]) là " << calcMaxProdValue(arr, n);
    return 0;
}

Kết quả đầu ra

Giá trị lớn nhất của abs(i-j)*min(arr[i],arr[j]) là 16