หาผลรวมค่าสัมบูรณ์ติดกันสูงสุดหลังกลับลำดับย่อยได้ 1 ครั้งใน C++

บทนำ

ในบทช่วยสอนนี้ เราจะหา ค่าสูงสุดของผลรวม |nums[i+1] - nums[i]| หลังจากทำ การกลับลำดับ (reverse) ย่อยหนึ่งช่วง (subarray) ได้สูงสุด 1 ครั้ง

ตัวอย่าง

Input: nums = [2, 4, 6]
Output: 6
กลับ [4, 6] → [2, 6, 4] → |2-6| + |6-4| = 4 + 2 = 6

อัลกอริทึม

พิจารณาผลของการ reverse subarray [l, r] ต่อผลรวมค่าสัมบูรณ์ติดกัน:

• เฉพาะขอบเขต l-1↔l และ r↔r+1 ที่เปลี่ยนแปลง
• ภายใน subarray ค่าสัมบูรณ์ไม่เปลี่ยน (แค่ลำดับกลับ)
• ลองทุกกรณีขอบเขตที่เป็นไปได้เพื่อหาค่าสูงสุด

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

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

int solve(vector& 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;
    
    // กรณี reverse prefix/suffix
    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]));
    }
    
    // กรณี reverse subarray กลาง (4 รูปแบบเครื่องหมาย)
    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 v = {2, 4, 6};
    cout << solve(v);
    return 0;
}

ผลลัพธ์

6

สรุป

อัลกอริทึม O(n) พิจารณาการเปลี่ยนแปลงที่ขอบเขตของ subarray ที่ reverse ใช้การจัดเก็บค่าสูงสุดของ 4 รูปแบบเครื่องหมาย (±nums[i] ± nums[i-1]) หากมีคำถาม สามารถถามได้ในส่วนความคิดเห็นครับ