Array
Dynamic Programming
Description
You are given an integer array values
where values[i] represents the value of the ith
sightseeing spot. Two sightseeing spots i
and j
have a distance j - i
between them.
The score of a pair (i < j
) of sightseeing spots is values[i] + values[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: values = [8,1,5,2,6]
Output: 11
Explanation: i = 0, j = 2, values[i] + values[j] + i - j = 8 + 5 + 0 - 2 = 11
Example 2:
Input: values = [1,2]
Output: 2
Constraints:
2 <= values.length <= 5 * 104
1 <= values[i] <= 1000
Solutions
Solution 1
Python3 Java C++ Go TypeScript
class Solution :
def maxScoreSightseeingPair ( self , values : List [ int ]) -> int :
ans , mx = 0 , values [ 0 ]
for j in range ( 1 , len ( values )):
ans = max ( ans , values [ j ] - j + mx )
mx = max ( mx , values [ j ] + j )
return ans
class Solution {
public int maxScoreSightseeingPair ( int [] values ) {
int ans = 0 , mx = values [ 0 ] ;
for ( int j = 1 ; j < values . length ; ++ j ) {
ans = Math . max ( ans , values [ j ] - j + mx );
mx = Math . max ( mx , values [ j ] + j );
}
return ans ;
}
}
class Solution {
public :
int maxScoreSightseeingPair ( vector < int >& values ) {
int ans = 0 , mx = values [ 0 ];
for ( int j = 1 ; j < values . size (); ++ j ) {
ans = max ( ans , values [ j ] - j + mx );
mx = max ( mx , values [ j ] + j );
}
return ans ;
}
};
func maxScoreSightseeingPair ( values [] int ) ( ans int ) {
for j , mx := 1 , values [ 0 ]; j < len ( values ); j ++ {
ans = max ( ans , values [ j ] - j + mx )
mx = max ( mx , values [ j ] + j )
}
return
}
function maxScoreSightseeingPair ( values : number []) : number {
let ans = 0 ;
let mx = values [ 0 ];
for ( let j = 1 ; j < values . length ; ++ j ) {
ans = Math . max ( ans , values [ j ] - j + mx );
mx = Math . max ( mx , values [ j ] + j );
}
return ans ;
}
GitHub