Giả sử ta có hai mảng số nguyên cùng độ dài, ta phải tìm giá trị lớn nhất của: |arr1[i] - arr1[j]| + |arr2[i] - arr2[j]| + |i - j|. Giá trị lớn nhất được lấy trên tất cả 0 <= i, j < arr1.length. Ví dụ, hai mảng [1,2,3,4] và [-1,4,5,6] cho kết quả 13.
Để giải quyết, ta thực hiện các bước sau:
Định nghĩa phương thức getVal nhận mảng v.
maxVal := -inf, minVal := inf.
Với i từ 0 đến kích thước v:
minVal := min của v[i] và minVal.
maxVal := max của v[i] và maxVal.
Trả về maxVal - minVal.
Từ phương thức main, làm sau:
Tạo mảng ret kích thước 4.
n := kích thước arr1.
Với i từ 0 đến n - 1:
Chèn arr1[i] - arr2[i] + i vào ret[0].
Chèn arr1[i] + arr2[i] + i vào ret[1].
Chèn arr1[i] - arr2[i] - i vào ret[2].
Chèn arr1[i] + arr2[i] - i vào ret[3].
ans := -inf.
Với i từ 0 đến 3:
ans := max của ans và getVal(ret[i]).
Trả về ans.
Xem triển khai dưới đây để hiểu rõ hơn:
Ví dụ minh họa
#include <bits/stdc++.h> using namespace std; class Solution { public: int getVal(vector <int>& v){ int maxVal = INT_MIN; int minVal = INT_MAX; for(int i = 0; i < v.size(); i++){ minVal = min(v[i], minVal); maxVal = max(v[i], maxVal); } return maxVal - minVal; } int maxAbsValExpr(vector<int>& arr1, vector<int>& arr2) { vector <int> ret[4]; int n = arr1.size(); for(int i = 0; i < n; i++){ ret[0].push_back(arr1[i] - arr2[i] + i); ret[1].push_back(arr1[i] + arr2[i] + i); ret[2].push_back(arr1[i] - arr2[i] - i); ret[3].push_back(arr1[i] + arr2[i] - i); } int ans = INT_MIN; for(int i = 0; i < 4; i++){ ans = max(ans, getVal(ret[i])); } return ans; } }; main(){ vector<int> v1 = {1,2,3,4}, v2 = {-1, 4, 5, 6}; Solution ob; cout << (ob.maxAbsValExpr(v1, v2)); }Đầu vào
[1,2,3,4] [-1,4,5,6]
Kết quả
13