[LeetCode] 1425. Constrained Subsequence Sum

https://leetcode.com/problems/constrained-subsequence-sum/description/

Constrained Subsequence Sum - LeetCode

leetcode - Constrained Subsequence Sum

문제 유형 : 슬라이딩 윈도우 / 부분합

문제 난이도 : Hard

 

문제

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.

 

정수 배열 nums와 정수 k가 주어집니다. 

요소들 간에 연결된 부속배열을 만들어서 그 합의 최대값을 구하시오. 값이 적어도 하나는 있어야 합니다.

여기서 연결됨은 두 요소 간의 인덱스 차이가 k 이하임을 말합니다.

배열의 순서를 변경할 수 없습니다.

 

풀이

덱을 하나 생성합니다.

이 덱의 첫 번째에는 지금까지 만든 부속배열의 합들이 담길 것 입니다.

 

반복자를 0부터 끝까지 반복하면서 다음의 과정을 반복합니다:

 1. nums[i]에 덱의 맨 첫번째 요소만큼 더합니다. 이러면 nums[i]에는 기존 nums[i]를 포함한 부속배열의 합이 담깁니다.

 2. 덱의 뒤부터, nums[i]보다도 작은 요소가 있다면 더 볼 필요가 없으므로 제거합니다.

 3. 만약 nums[i]가 양수라면, 더 큰 합이 생기는 것이므로 덱에 넣어줍니다.

 4. 만약 덱의 맨 앞의 요소가 k+1칸 더 앞에 있는 요소의 값이라면,  범위를 벗어났으므로 없애줍니다.

 

이를 계속 반복합니다.

 

nums에는 기존 nums의 요소 자신이 포함된 최고로 높은 부속배열의 값이 들어있습니다. 

nums배열에서 가장 큰 값을 반환합니다.

 

 

코드

C++

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        deque<int> subsequenceSum;

        for (int i = 0; i < nums.size(); i++) {
            nums[i] += !subsequenceSum.empty() ? subsequenceSum.front() : 0;

            while (!subsequenceSum.empty() && nums[i] > subsequenceSum.back()) {
                subsequenceSum.pop_back();
            }

            if (nums[i] > 0) {
                subsequenceSum.push_back(nums[i]);
            }

            if (i >= k && !subsequenceSum.empty() && subsequenceSum.front() == nums[i - k]) {
                subsequenceSum.pop_front();
            }
        }

        return *max_element(nums.begin(), nums.end());
    }
};