1014. 最佳觀光組合
題目分析
題目給定的觀光景點(diǎn)評(píng)分公式是dp = A[i] + A[j] + i - j
督怜,變化一下可以得到A[i] + i
和A[j] - j
滨达。
我們可以發(fā)現(xiàn)轻黑,在遍歷的過(guò)程中,只要固定了i
和j
,前后兩個(gè)式子就不會(huì)變。所以我們可以遍歷原數(shù)組森逮,在遍歷的過(guò)程中不斷更新A[i] + i
的最大值以及dp
。
遍歷過(guò)程如下:
for (int i = 1; i < A.size(); i++) {
res = res > temp + A[j] - j ? res : temp + A[j] - j;
temp = temp > A[j] + j ? temp : A[j] + j;
}
最后返回res
即可磁携。
題目解答
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& A) {
int res = INT_MIN;
int temp = A[0] + 0;
for (int j = 1; j < A.size(); j++) {
res = res > temp + A[j] - j ? res : temp + A[j] - j;
temp = temp > A[j] + j ? temp : A[j] + j;
}
return res;
}
};