Đảo ngược mảng con để tối đa giá trị mảng trong C++

Cho mảng nums. Giá trị mảng = tổng |nums[i]-nums[i+1]| với i từ 0 đến n-2. Có thể chọn một mảng con và đảo ngược nó (chỉ 1 lần). Tìm giá trị lớn nhất có thể của mảng sau thao tác.

Ví dụ: [1,5,4,2,3] → đầu ra 10.

Giải pháp

Phân tích thay đổi giá trị khi đảo mảng con [l, r]:

• Giá trị ban đầu: sum = Σ|a[i]-a[i+1]|
• Đảo mảng con chỉ ảnh hưởng đến các cạnh tại l-1/l và r/r+1
• Tính extra = max tăng thêm có thể đạt được:
  • Đảo từ đầu: |nums[0]-b| - |a-b| với a=nums[l], b=nums[l+1]
  • Đảo đến cuối: |nums[n-1]-a| - |a-b|
  • Đảo giữa: 2*(max(min(a,b)) - min(max(a,b))) cho các cặp liên tiếp
• Kết quả = sum + max(extra, 2*(maxVal - minVal))

Ví dụ mã C++

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

class Solution { 
public: 
    int maxValueAfterReverse(vector<int>& nums) { 
        int ret = 0; 
        int extra = 0; 
        int n = nums.size(); 
        int minVal = INT_MAX; 
        int maxVal = INT_MIN; 
        
        for(int i = 0; i < n - 1; i++) { 
            int a = nums[i]; 
            int b = nums[i + 1]; 
            ret += abs(b - a); 
            extra = max(extra, abs(nums[0] - b) - abs(a - b)); 
            extra = max(extra, abs(nums[n - 1] - a) - abs(a - b)); 
            maxVal = max(maxVal, min(a, b)); 
            minVal = min(minVal, max(a, b)); 
        } 
        
        return ret + max(extra, (maxVal - minVal) * 2); 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {1,5,4,2,3}; 
    cout << (ob.maxValueAfterReverse(v)); 
    return 0; 
}

Đầu vào

{1,5,4,2,3}

Đầu ra

10