Skip to content

Latest commit

 

History

History
46 lines (33 loc) · 2.08 KB

README.md

File metadata and controls

46 lines (33 loc) · 2.08 KB

< Previous 　　　　　　　　　　　　　　　　 Next >

1014. Best Sightseeing Pair (Medium)

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:

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

Related Topics

[Array]

Hints

Hint 1 Can you tell the best sightseeing spot in one pass (ie. as you iterate over the input?) What should we store or keep track of as we iterate to do this?