Best Sightseeing Pair ใน C++

คำอธิบายปัญหา

กำหนดอาร์เรย์ A ของจำนวนเต็มบวก A[i] = ค่าของสถานที่ท่องเที่ยวที่ i ระยะห่างระหว่าง i และ j คือ j-i คะแนนของคู่ (i

ตัวอย่าง: [8,1,5,2,6] → 11 (i=0, j=2: 8+5+0-2=11)

วิธีแก้ปัญหา (One Pass)

จัดรูปสูตร: (A[i] + i) + (A[j] - j)

1. เก็บค่า maxVal = max(A[k] + k) สำหรับ k < i
2. สำหรับแต่ละ i คำนวณคะแนน = maxVal + A[i] - i
3. อัปเดตคำตอบและ maxVal

Complexity: O(n) เวลา, O(1) พื้นที่

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

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

class Solution {
public:
    int maxScoreSightseeingPair(vector<int>& A) {
        int ret = 0;
        int maxVal = 0;
        int n = A.size();
        
        for(int i = 0; i < n; i++) {
            ret = max(ret, maxVal + A[i] - i);
            maxVal = max(maxVal, A[i] + i);
        }
        return ret;
    }
};

int main() {
    vector<int> v1 = {8, 1, 5, 2, 6};
    Solution ob;
    cout << ob.maxScoreSightseeingPair(v1);
    return 0;
}

อินพุต

[8,1,5,2,6]

เอาต์พุต

11