原題#
https://leetcode.cn/problems/best-sightseeing-pair/description/
思路#
双循环枚举
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int max = 0;
int length = values.size();
for(int i = 0; i < length; ++i)
for(int j = i + 1; j < length; ++j)
if(values[i] + values[j] + i - j > max)
max = values[i] + values[j] + i - j;
return max;
}
};
但不能通过全部测试点。时间复杂度过高
题解#
思路:降低复杂度。想办法弄成 的复杂度就好了。
目标函数移项得到 (value[i] + i) + (value[j] - j)
,然后将 value[i] + i
当做整体,将 value[j] - j
当做整体。就转化为了两数的最大值。
考虑遍历 j
然后维护 value[i] + i
的最大值,所以代码可以变为
class Solution {
public:
int maxScoreSightseeingPair(vector<int>& values) {
int ans = 0;
int mx = 0;
for(int j = 0; j < values.size(); ++j){
ans = max(ans, mx + values[j] - j);
mx = max(mx, values[j] + j);
}
return ans;
}
};
枚举右维护左#
对于类似 leetcode 1014 所示的双变量问题,可以选择枚举右下标 ,来转化为单变量问题求解。