Leetcode 3205. Maximum Array Hopping Score I

문제

Given an array nums, 
you have to get the maximum score starting from index 0 
and hopping until you reach the last element of the array.

In each hop, 
you can jump from index i to an index j > i, 
and you get a score of (j - i) * nums[j].

Return the maximum score you can get.

양의 정수 배열 arr이 주어진다.
사용자는 index i 에서 index j로 점프할수 있는데 ( i < j )
점프시 (j - i) * arr[j] 만큼의 점수를 얻는다.
얻을수 있는 최대 점수를 구하시오.

예시

[4,5,2,8,9,1,3]
- 0 > 4 > 6 번 index로 점프한다.
- 42의 점수를 얻는다.

제한

• $2 <= nums.length <= 10^3$
• $1 <= nums[i] <= 10^5$

풀이법

• 거꾸로 생각해야 한다.
• j번째 index를 목표로 점프하면 한칸당 j의 점수를 얻는다
• 즉 도착하는 지점의 값이 계속 최대가 되게 하면서 점프를 했을때 점수를 계속 더해 나가면 된다.
• 즉 한칸 한칸마다 최대 값을 더하도록 이어나가면 된다.

class Solution:
    def maxScore(self, nums: List[int]) -> int:
        res, mx = 0, 0
        # 거꾸로 loop
        for num in nums[:0:-1]:
        	# mx는 한칸 점프시 얻을수 있는 최대의 점수를 계속 업데이트한다.
            mx = max(mx, num)
            # 한칸 점프 값만큼 더한다.
            res += mx
        return res