Cho mảng A số nguyên dương, A[i] là giá trị điểm tham quan i, khoảng cách giữa i và j là j - i. Điểm của cặp (i < j) là A[i] + A[j] + i - j. Tìm điểm tối đa.
Ví dụ: [8,1,5,2,6] → 11 (i=0, j=2: 8+5+0-2=11).
Giải pháp O(n):
ret := 0, maxVal := 0, n := size của A
Với i từ 0 đến n-1:
ret = max(ret, maxVal + A[i] - i)
maxVal = max(maxVal, A[i] + i)Trả về ret
Ý tưởng: maxVal lưu max(A[k] + k) cho k < i, khi xét j=i, ta cần max(A[k]+k) + A[i] - i.
Ví dụ
#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(A[i] + i, maxVal); } return ret; } }; int main(){ vector<int> v1 = {8, 1, 5, 2, 6}; Solution ob; cout << (ob.maxScoreSightseeingPair(v1)); }Đầu vào
[8,1,5,2,6]
Đầu ra
11