首页 📝 算法学习

题目传送门

https://leetcode-cn.com/problems/best-sightseeing-pair/

题意

给定一个数组, 其中一对观光景点的得分是通过公式 $v_i + v_j + i - j (i < j)$ 得到的, 问能够得到的最高得分

思路

简单 $dp$ , 首先预处理出 $v_i + i$ 记为数组 $a$ 和 $v_i - i$ 记为数组 $b$ 的值, 然后从前往后遍历, 记录一下第 $i$ 个位置之前 $a_i$ 的最大值记为 $maxx$, 转移方程 $ans = max(ans, b_i + maxx); maxx = max(maxx, a_i)$

代码

class Solution {
    public:
    int maxScoreSightseeingPair(vector<int>& values) {
        int ans = -0x7f7f7f7f, maxx = -0x7f7f7f7f;
        if(values.size() == 1) return 0;
        vector<int> a, b;
        for(int i = 0; i < values.size(); i++)
            a.push_back(values[i] + i), b.push_back(values[i] - i);
        maxx = a[0];
        for(int i = 1; i < values.size(); i++){
            ans = max(ans, b[i] + maxx);
            maxx = max(maxx, a[i]);
        }
        return ans;
    }
};



文章评论