【LeetCode】最佳观光组合

题目

给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。

一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。

返回一对观光景点能取得的最高分。

暴力求解（超时）

我们直接模拟运算，直接双重循环遍历出最后结果

 int maxScoreSightseeingPair(vector<int>& A) {int ans = 0;for (int i = 0; i < A.size(); i++) {for (int j = i+1; j < A.size(); j++) {ans = max(ans, A[i] + A[j] + i - j);}}return ans;}

枚举方法

由于得分为（A[i] + A[j] + i - j）
我们可以分解成**（A[i]+i）+(A[j]-j)**
我们可以在一次遍历的过程中维护一个A[i]+i的最大值
之后再进行 计算即可

    int maxScoreSightseeingPair(vector<int>& A) {int ans = 0;int mx = A[0] + 0;for (int i = 1; i < A.size(); i++) {ans = max(mx + A[i] - i, ans);mx = max(mx, i + A[i]);//维护的 A[i]+i}return ans;}

复杂度分析

时间复杂度O(N)
空间复杂度O(1)

希望我所写的对大家有用