nums라는 숫자 목록이 있다고 가정하고 엄격하게 증가하는 값의 하위 시퀀스를 선택합니다. 여기서 각 두 숫자의 차이는 두 인덱스의 차이와 같습니다. 따라서 이러한 부분 수열의 최대 합을 찾아야 합니다.
따라서 입력이 nums =[6, 7, 9, 9, 8, 5]와 같으면 인덱스가 [0, 1, 삼]. 각 연속 숫자의 차이는 [1, 2]이며 인덱스의 차이와 동일합니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
d :=빈 지도
-
숫자로 된 각 인덱스 i와 값 x에 대해 수행
-
d[x − i] :=d[x − i] + x
-
-
d
의 모든 값의 최대값을 반환합니다.
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
class Solution: def solve(self, nums): from collections import defaultdict d = defaultdict(int) for i, x in enumerate(nums): d[x − i] += x return max(d.values()) ob1 = Solution() nums = [6, 7, 9, 9, 8, 5] print(ob1.solve(nums))
입력
[6, 7, 9, 9, 8, 5]
출력
22