1425. Constrained Subsequence Sum
https://leetcode.com/problems/constrained-subsequence-sum/?envType=daily-question&envId=2023-10-21
1) 문제 설명
Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence of that array such that for every two consecutive integers in the subsequence, nums[i] and nums[j], where i < j, the condition j - i <= k is satisfied.
A subsequence of an array is obtained by deleting some number of elements (can be zero) from the array, leaving the remaining elements in their original order.
2) 제한 사항
- 1 <= k <= nums.length <= 105
- -104 <= nums[i] <= 104
3) 도전 과제
X
4) 풀이
문제를 이해하는 게 굉장히 어려웠다.
처음에는 시작점을 잡고 max를 비교하는 방식으로 하려 했으나, 시작점+k보다 더 큰 인덱스를 살펴볼 수 없어서 기각하였다.
두 번째로 생각한 풀이는 가능한 모든 배열의 조합을 구한 후, 그 속에서 최대값을 비교하는 방식이었다. 배열의 조합을 구할 때 현재 위치에서 1~k 까지의 선택지가 있는데, 이를 그림으로 그리면 트리 형태가 나온다. (다만 본 문제에서 요구하는 트리가 어떤 트리인지는 아직 정확히 모르겠다.)
그래서 트리를 먼저 그린 후, 시작점과 끝점을 지정한 채로 트리 전체를 순회하여 최댓값을 비교하려고 하였다.
231021 - 위 풀이를 떠올리긴 했으나, 트리를 구현하는 것에서 막힘.
5) 소스 코드 및 결과
'알고리즘 풀이' 카테고리의 다른 글
| 231023 LeetCode 문제 풀이 (0) | 2023.10.23 |
|---|---|
| 231022 LeetCode 문제 풀이 (0) | 2023.10.23 |
| 231020 LeetCode 문제 풀이 (스택) (2) | 2023.10.20 |
| 221124 알고리즘 풀이 1문제 (2) | 2022.11.24 |
| 221123 알고리즘 풀이 6문제 (0) | 2022.11.23 |
