做网站服务器需要系统,做网站要注意什么问题,公司网站建设周期及费用,wordpress 3 403【问题描述】[中等]
给定正整数数组 A#xff0c;A[i] 表示第 i 个观光景点的评分#xff0c;并且两个景点 i 和 j 之间的距离为 j - i。一对景点#xff08;i j#xff09;组成的观光组合的得分为#xff08;A[i] A[j] i - j#xff09;#xff1a;景点的评分之…【问题描述】[中等]
给定正整数数组 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
【解答思路】
1. 暴力 双重循环超时
从前往后 两层循环 时间复杂度O(N^2) 空间复杂度O(1) public int maxScoreSightseeingPair(int[] A) {if(A.length 0){return 0;}int max 0;for(int i 0 ; i A.length;i){for(int j i1 ; j A.length;j){max Math.max(max,A[i] A[j] i - j);}}return max ;}2. 暴力优化
ans A[i]i 和 A[j]-jA[j]−j
由于 A[j]-j 是固定不变的因此最大化 A[i]iA[j]-j的值其实就等价于求 [0,j-1][0,j−1] 中 A[i]i 的最大值 mx景点 j的答案即为 mxA[j]-jmx 的值我们只要从前往后枚举 j 的时候同时维护即可
时间复杂度O(N) 空间复杂度O(1) public int maxScoreSightseeingPair(int[] A) {
int ans 0, mx A[0] 0;for (int j 1; j A.length; j) {ans Math.max(ans, mx A[j] - j);// 边遍历边维护 有ij 的限制mx Math.max(mx, A[j] j);}return ans;}【总结】
1.暴力解决后优化是解题重要思想
2.暴力优化 公式变换 前缀和等思想
