[Leedcode][JAVA][第1014题][最佳观光组合][数组][暴力优化]

た入场券 2023-02-18 09:40 121阅读 0赞

#### 【问题描述】\[中等\] ####

给定正整数数组 A，A[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 = i+1 ; 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\]+i+A\[j\]-j的值其实就等价于求 \[0,j-1\]\[0,j−1\] 中 A\[i\]+i 的最大值 mx，景点 j的答案即为 mx+A\[j\]-j
 *  mx 的值我们只要从前往后枚举 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);
    
                // 边遍历边维护 有i<j 的限制
                mx = Math.max(mx, A[j] + j);
            }
            return ans;
            }

#### 【总结】 ####

###### 1.暴力解决后优化是解题重要思想 ######

###### 2.暴力优化 公式变换 前缀和等思想 ######

![在这里插入图片描述][20200617090730202.png]

[20200617090730202.png]: https://img-blog.csdnimg.cn/20200617090730202.png