1425. Constrained Subsequence Sum

• 전혀 풀이 방법을 생각하지 못한 문제.
• 각 index에 대해서 이전 index까지의 최대 합 + 현재 index의 값을 선택하는 경우, 아닌 경우를 추적하여 최대 합을 구하는 방식으로 풀어보려고 했지만 도저히 점화식을 만드는 방법이 생각이 안 나서 실패함.

• Monotone queue를 활용해야 한다.
• Queue에는 숫자의 index 값을 유지한다.
• Queue의 앞쪽에는 조건을 만족하는 (가장 큰) subset sum 값을 가리키는 index가 위치하도록 한다.
• 이를 위해서 queue의 뒤쪽에 현재 위치의 subset sum nums[i] 보다 작은 값이 있는 경우 모두 제거한다.
• 그 다음 queue에 현재 subset sum nums[i] 값을 넣는다.
• 이렇게 하면 queue에 있는 값은 항상 단조 감소하는 형태로 유지된다.

• 선입선출이므로 queue의 앞에 있는 index가 가장 작은 index 값이된다. 이 값이 범위 k를 벗어난 경우 제거한다.

class Solution {
public:
    int constrainedSubsetSum(vector<int>& nums, int k) {
        deque<int> indices;
        int result = nums[0];
        for (int i = 0; i < nums.size(); ++i) {
            nums[i] += !indices.empty()? nums[indices.front()] : 0;
            result = max(result, nums[i]);

            while (!indices.empty() && nums[i] > nums[indices.back()])
                indices.pop_back();

            if (nums[i] > 0)
                indices.push_back(i);

            if (!indices.empty() && i - indices.front() >= k)
                indices.pop_front();
        }
        return result;
    }
};