Giả sử ta có danh sách nums và có thể đảo ngược một dãy con bất kỳ tối đa một lần. Sau phép toán này, ta phải tìm giá trị lớn nhất có thể của
$\displaystyle\sum\limits_{i=0}^{n-2}| nums[i+1]-[nums[i]|$
Ví dụ: nums = [2, 4, 6], đầu ra = 6, vì đảo [4, 6] ta được [2, 6, 4] và |2-6| + |6-4| = 6.
Để giải quyết, ta làm theo các bước:
- Nếu kích thước nums ≤ 1, trả về 0.
- ans := 0.
- n := kích thước nums.
- for i := 1; i < n; ++i: ans += |nums[i] - nums[i-1]|.
- orig := ans.
- for i := 1; i < n-1; ++i:
- ans = max(ans, orig - |nums[i] - nums[i+1]| + |nums[0] - nums[i+1]|).
- ans = max(ans, orig - |nums[i] - nums[i-1]| + |nums[n-1] - nums[i-1]|).
- pp := -|nums[1] - nums[0]| + nums[0] + nums[1].
- pm := -|nums[1] - nums[0]| + nums[0] - nums[1].
- mp := -|nums[1] - nums[0]| - nums[0] + nums[1].
- mm := -|nums[1] - nums[0]| - nums[0] - nums[1].
- for j := 2; j < n-1; ++j:
- jerror := |nums[j+1] - nums[j]|.
- ans = max(ans, orig + pp - jerror - nums[j] - nums[j+1]).
- ans = max(ans, orig + pm - jerror - nums[j] + nums[j+1]).
- ans = max(ans, orig + mp - jerror + nums[j] - nums[j+1]).
- ans = max(ans, orig + mm - jerror + nums[j] + nums[j+1]).
- pp = max(pp, -|nums[j] - nums[j-1]| + nums[j-1] + nums[j]).
- pm = max(pm, -|nums[j] - nums[j-1]| + nums[j-1] - nums[j]).
- mp = max(mp, -|nums[j] - nums[j-1]| - nums[j-1] + nums[j]).
- mm = max(mm, -|nums[j] - nums[j-1]| - nums[j-1] - nums[j]).
- Trả về ans.
Xem triển khai dưới đây:
Ví dụ
#include <bits/stdc++.h> using namespace std; int solve(vector<int>& nums) { if (nums.size() <= 1) return 0; int ans = 0; int n = nums.size(); for (int i = 1; i < n; i++) { ans += abs(nums[i] - nums[i - 1]); } int orig = ans; for (int i = 1; i < n - 1; i++) { ans = max(ans, orig - abs(nums[i] - nums[i + 1]) + abs(nums[0] - nums[i + 1])); ans = max(ans, orig - abs(nums[i] - nums[i - 1]) + abs(nums[n - 1] - nums[i - 1])); } int pp = -abs(nums[1] - nums[0]) + nums[0] + nums[1]; int pm = -abs(nums[1] - nums[0]) + nums[0] - nums[1]; int mp = -abs(nums[1] - nums[0]) - nums[0] + nums[1]; int mm = -abs(nums[1] - nums[0]) - nums[0] - nums[1]; for (int j = 2; j < n - 1; j++) { int jerror = abs(nums[j + 1] - nums[j]); ans = max(ans, orig + pp - jerror - nums[j] - nums[j + 1]); ans = max(ans, orig + pm - jerror - nums[j] + nums[j + 1]); ans = max(ans, orig + mp - jerror + nums[j] - nums[j + 1]); ans = max(ans, orig + mm - jerror + nums[j] + nums[j + 1]); pp = max(pp, -abs(nums[j] - nums[j - 1]) + nums[j - 1] + nums[j]); pm = max(pm, -abs(nums[j] - nums[j - 1]) + nums[j - 1] - nums[j]); mp = max(mp, -abs(nums[j] - nums[j - 1]) - nums[j - 1] + nums[j]); mm = max(mm, -abs(nums[j] - nums[j - 1]) - nums[j - 1] - nums[j]); } return ans; } int main(){ vector<int> v = {2, 4, 6}; cout << solve(v); }
Đầu vào
{2, 4, 6}
Đầu ra
6