ค่าสูงสุดของ Absolute Value Expression ใน C++

ปัญหา

ให้ Array arr1, arr2 ขนาดเท่ากัน หาค่าสูงสุดของ:

|arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|

สำหรับทุกคู่ i, j

ตัวอย่าง

arr1 = [1,2,3,4], arr2 = [-1,4,5,6] → Output = 13

วิธีแก้: แปลง Absolute Value

Expression = max ของ 4 กรณี (จากการกำจัด | |):

Case 1:  (arr1[i] - arr2[i] + i) - (arr1[j] - arr2[j] + j)
Case 2:  (arr1[i] + arr2[i] + i) - (arr1[j] + arr2[j] + j)
Case 3:  (arr1[i] - arr2[i] - i) - (arr1[j] - arr2[j] - j)
Case 4:  (arr1[i] + arr2[i] - i) - (arr1[j] + arr2[j] - j)

แต่ละ Case = Max - Min ของ Array นั้น → หา Max-Min ของ 4 Array แล้วหา Max ของทั้ง 4

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int getVal(vector<int>& v) {
        int maxVal = INT_MIN, minVal = INT_MAX;
        for (int x : v) {
            maxVal = max(maxVal, x);
            minVal = min(minVal, x);
        }
        return maxVal - minVal;
    }
    
    int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) {
        int n = arr1.size();
        vector<int> v[4];
        
        for (int i = 0; i < n; i++) {
            v[0].push_back(arr1[i] - arr2[i] + i);
            v[1].push_back(arr1[i] + arr2[i] + i);
            v[2].push_back(arr1[i] - arr2[i] - i);
            v[3].push_back(arr1[i] + arr2[i] - i);
        }
        
        int ans = INT_MIN;
        for (int i = 0; i < 4; i++)
            ans = max(ans, getVal(v[i]));
        
        return ans;
    }
};

int main() {
    vector<int> v1 = {1,2,3,4}, v2 = {-1,4,5,6};
    Solution ob;
    cout << ob.maxAbsValExpr(v1, v2) << endl; // 13
    return 0;
}

ผลลัพธ์

13

การตรวจสอบ

i=0, j=3: |1-4| + |-1-6| + |0-3| = 3 + 7 + 3 = 13 ✓

ความซับซ้อน

• Time: O(N)
• Space: O(N)