定州网站建设公司,企业建立网站的好处,了解做房产广告的网站,住房和城乡建设部网站安广东省1. 题目
给定正整数数组 A#xff0c;A[i] 表示第 i 个观光景点的评分#xff0c;并且两个景点 i 和 j 之间的距离为 j - i。
一对景点#xff08;i j#xff09;组成的观光组合的得分为#xff08;A[i] A[j] i - j#xff09;#xff1a;景点的评分之和减去它…1. 题目
给定正整数数组 AA[i] 表示第 i 个观光景点的评分并且两个景点 i 和 j 之间的距离为 j - i。
一对景点i j组成的观光组合的得分为A[i] A[j] i - j景点的评分之和减去它们两者之间的距离。
返回一对观光景点能取得的最高分。
示例
输入[8,1,5,2,6]
输出11
解释i 0, j 2, A[i] A[j] i - j 8 5 0 - 2 11提示
2 A.length 50000
1 A[i] 1000来源力扣LeetCode 链接https://leetcode-cn.com/problems/best-sightseeing-pair 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。
2. 解题
暴力解法看A的长度很大会超时
class Solution {
public:int maxScoreSightseeingPair(vectorint A) {int i, j, scores 0;for(i 0; i A.size(); i){for(j i1; j A.size(); j)scores max(scores, A[i]A[j]i-j);}return scores;}
};class Solution {
public:int maxScoreSightseeingPair(vectorint A) {int i, scoresA A[0]0, scores 0;for(i 1; i A.size(); i){scores max(scores, scoresA A[i]-i);//历史的A的得分当前的B得分scoresA max(scoresA, A[i]i); //记录最大的A点得分}return scores;}
};
