|
| 1 | +#!/usr/bin/python3 |
| 2 | +""" |
| 3 | +Given an array A of positive integers, A[i] represents the value of the i-th |
| 4 | +sightseeing spot, and two sightseeing spots i and j have distance j - i between |
| 5 | +them. |
| 6 | +
|
| 7 | +The score of a pair (i < j) of sightseeing spots is (A[i] + A[j] + i - j) : the |
| 8 | +sum of the values of the sightseeing spots, minus the distance between them. |
| 9 | +
|
| 10 | +Return the maximum score of a pair of sightseeing spots. |
| 11 | +
|
| 12 | +Example 1: |
| 13 | +
|
| 14 | +Input: [8,1,5,2,6] |
| 15 | +Output: 11 |
| 16 | +Explanation: i = 0, j = 2, A[i] + A[j] + i - j = 8 + 5 + 0 - 2 = 11 |
| 17 | +
|
| 18 | +
|
| 19 | +Note: |
| 20 | +2 <= A.length <= 50000 |
| 21 | +1 <= A[i] <= 1000 |
| 22 | +""" |
| 23 | +fromtypingimportList |
| 24 | + |
| 25 | + |
| 26 | +classSolution: |
| 27 | +defmaxScoreSightseeingPair(self,A:List[int])->int: |
| 28 | +""" |
| 29 | + Attribute the result to the ending element |
| 30 | +
|
| 31 | + Count the current best score in all previous. |
| 32 | + Distance will increase, then the score will decay |
| 33 | + """ |
| 34 | +ret=-float("inf") |
| 35 | +prev_max=A[0] |
| 36 | +forainA[1:]: |
| 37 | +ret=max(ret,prev_max-1+a) |
| 38 | +prev_max=max(prev_max-1,a) |
| 39 | + |
| 40 | +returnret |
| 41 | + |
| 42 | +defmaxScoreSightseeingPair_error(self,A:List[int])->int: |
| 43 | +""" |
| 44 | + brute force O(N^2) |
| 45 | +
|
| 46 | + pre-processing, adjust A[i] as A[i] - i |
| 47 | + error, no direction |
| 48 | + """ |
| 49 | +n=len(A) |
| 50 | +B= [] |
| 51 | +foriinrange(n): |
| 52 | +B.append(A[i]-i) |
| 53 | + |
| 54 | +# find top 2 |
| 55 | +m1,m2=None,None |
| 56 | +foriinrange(n): |
| 57 | +ifm1isNone: |
| 58 | +m1=i |
| 59 | +elifm2isNone: |
| 60 | +m2=i |
| 61 | +elifB[i]+ (i-m1)>B[m1]: |
| 62 | +m1=i |
| 63 | +elifB[i]+ (i-m2)>B[m2]: |
| 64 | +m2=i |
| 65 | +returnA[m2]+A[m1]-abs(m2-m1) |
| 66 | + |
| 67 | + |
| 68 | +if__name__=="__main__": |
| 69 | +assertSolution().maxScoreSightseeingPair([8,1,5,2,6])==11 |