每日一题_动态规划_1014_最佳观光组合

前言

date: 8.7

昨晚又是2点多睡，困困困~

题目来源: 1014. 最佳观光组合(leetcode)

汇总文章 每日一题系列_算法提升

题目

题解

这里要求 $i<j$ 情况下, $max(values[i]+values[j]+i-j)$,
我们可以拆分成 $max(values[i]+i)+max(values[j]+j)$
并且由于 i < j, 实际上我们可以遍历一次数组即可。
前者先设置初始值为values[0] + 0,
然后再判断整个式子是否更大(若是则更新)，
接着判断是否 $values[i]+i$更大(若是则更新)。

class Solution {
public:int maxScoreSightseeingPair(vector<int>& values) {int viMax = values[0] + 0, ans = 0;for (int i = 1; i < values.size(); i++) {// 由于一对观光点前者要小于后者, 因此先更新ans， 再更新viMaxans = max(ans, viMax + values[i] - i);viMax = max(viMax, values[i] + i);} return ans;}
};