leetcode之每日一题

leetcode 1014

最佳观光组合

Posted by Static on June 17, 2020

题目链接:https://leetcode-cn.com/problems/best-sightseeing-pair/

题目描述

分析

1. 循环

A[i] + A[j] + i - j 等价于 A[i] + i + A[j]-j 满足 (j > i)，一次循环可计算出结果

代码实现

public enum Q1014 {
    instance;

    // O(n)
    // A[i] + A[j] + i - j = A[i] + i + A[j]-j , (j > i)
    public int maxScoreSightseeingPair(int[] A) {
        int leftMax=A[0], max=Integer.MIN_VALUE;
        for (int j = 1; j < A.length; j++) {
            int c=leftMax+A[j]-j;
            max=max>c?max:c;

            int left=A[j]+j;
            leftMax =leftMax>left?leftMax:left;
        }
        return max;
    }

    // 时间复杂度过高 O(n^2)
    public int maxScoreSightseeingPair1(int[] A) {
        int max=Integer.MIN_VALUE;
        int l=A.length;
        for(int i=0;i<l;i++){
            for(int j=i+1;j<l;j++){
                int n=A[i]+A[j]+i-j;
                max=n>max?n:max;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        // assert 11
        System.out.println(Q1014.instance.maxScoreSightseeingPair(new int[]{8,1,5,2,6}));
        System.out.println(Q1014.instance.maxScoreSightseeingPair1(new int[]{8,1,5,2,6}));
    }
}