หาค่า Max ของ abs(i-j) * min(arr[i], arr[j]) ในอาร์เรย์ C++

คำอธิบายปัญหา

ได้รับอาร์เรย์ arr[] ขนาด N ต้องการหา ค่าสูงสุดของ abs(i - j) * min(arr[i], arr[j]) สำหรับคู่ดัชนี i, j ใดๆ

ตัวอย่าง

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

Output: 16

คำอธิบาย: ค่าสูงสุดคือ 16 ที่ index 0 และ 4 → abs(0-4) * min(5,4) = 4 * 4 = 16

แนวทางแก้ปัญหา

วิธีที่ 1: Brute Force (Two Nested Loops)

ตรวจสอบทุกคู่ i, j → Time: O(n²)

วิธีที่ 2: Two Pointers (มีประสิทธิภาพ O(n))

ใช้ตัวชี้สองตัว: start = 0 (หน้า) และ end = n-1 (หลัง)

• คำนวณค่า currentVal = min(arr[start], arr[end]) * (end - start)
• อัปเดต maxVal
• ถ้า arr[start] < arr[end] → start++ (เพราะค่าต่ำกว่าจำกัดผลคูณ ลองหาค่ามากกว่าด้านหน้า)
• มิฉะนั้น → end--
• ทำซ้ำจน start >= end

เหตุผล: การย้าย Pointer ที่มีค่าน้อยกว่าให้โอกาสหาค่าที่ใหญ่ขึ้น ซึ่งอาจให้ผลคูณมากขึ้น แม้ระยะทางจะสั้นลง

โค้ดตัวอย่าง C++

#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