กลับลำดับ Subarray เพื่อเพิ่มค่าอาร์เรย์สูงสุดใน C++

คำอธิบายโจทย์

ค่าของอาร์เรย์ = Σ|nums[i]-nums[i+1]| สามารถเลือก subarray ใดๆ 1 ช่วงแล้วกลับลำดับได้ 1 ครั้ง หาค่าสูงสุดที่เป็นไปได้

ตัวอย่าง

nums = [1,5,4,2,3] → Output: 10

วิธีแก้ปัญหา

ค่าพื้นฐาน = Σ|a-b| การกลับ subarray ผลกระทบแค่ขอบเขต 2 จุด:

1. ขอบซ้าย: |nums[0]-b| - |a-b| (b=nums[i+1])
2. ขอบขวา: |nums[n-1]-a| - |a-b| (a=nums[i])
3. กลาง: เพิ่มได้สูงสุด 2×(max(min(a,b)) - min(max(a,b))) จากการกลับคู่ที่มีช่วงทับซ้อนมากที่สุด

คำตอบ = ค่าพื้นฐาน + max(extra, 2×(maxVal-minVal))

การทำงานของโค้ด

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

class Solution {
public:
    int maxValueAfterReverse(vector<int>& nums) {
        int ret = 0, extra = 0;
        int n = nums.size();
        int minVal = INT_MAX, maxVal = INT_MIN;
        
        for(int i=0; i

อินพุต
{1,5,4,2,3}

เอาต์พุต
10