1014. Best Sightseeing Pair.md

1014. Best Sightseeing Pair

---

leetcode-cn Daily Challenge on June 17, 2020.

---

Difficulty : Medium

Related Topics : Array

---

Given an array A of positive integers, A[i] represents the value of the i-th sightseeing spot, and two sightseeing spots i and j have distance j - i between them.

The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the sum of the values of the sightseeing spots, minus the distance between them.

Return the maximum score of a pair of sightseeing spots.

Example 1:

Input: [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11

Note:

• 2 <= A.length <= 50000
• 1 <= A[i] <= 1000

---

Solution

• mine
  • Java

    • Time Limited

      // O(N^2)time  O(1)space
      public int maxScoreSightseeingPair(int[] A) {
          int len = A.length;
          int res = 0;
          for(int i = 0; i < len; i++){
              for(int j = i + 1; j < len; j++){
                  res = Math.max(res, A[i] + A[j] + i - j);
              }
          }
          return res;
      }
      

    • Runtime: 2 ms, faster than 99.78%, Memory Usage: 48.1 MB, less than 55.78% of Java online submissions

      // O(N)time 
      // O(1)space
      public int maxScoreSightseeingPair(int[] A) {
          int left = A[0];
          int res = 0;
          for(int i = 1; i < A.length; i++){
              res = Math.max(res, left + A[i] - i);
              left = Math.max(left, A[i] + i);
          }
          return res;
      }
      

---