Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 풀어보는 제한된 부분 수열의 최대 합 문제

배열 nums와 정수 k가 주어졌을 때, 특정 조건을 만족하는 비어 있지 않은 부분 수열(subsequence) 중 합이 최대가 되는 값을 구하는 문제입니다.

조건은 다음과 같습니다. 부분 수열에서 인접한 두 원소 nums[i]와 nums[j](i < j)에 대해 항상 j - i <= k를 만족해야 합니다.

여기서 부분 수열이란 배열에서 일부 원소를 삭제한 뒤, 남은 원소들의 원래 순서를 그대로 유지한 것을 의미합니다.

예를 들어 입력이 [10, 2, -9, 5, 19]이고 k = 2라면, 부분 수열 [10, 2, 5, 19]를 선택했을 때 합이 36으로 최대가 됩니다.

문제 해결 접근 방법

이 문제는 동적 계획법(DP)과 슬라이딩 윈도우 최댓값 처리를 위한 덱(deque)을 결합하면 O(n) 시간 복잡도로 효율적으로 해결할 수 있습니다. 여기서 dp[i]는 i번째 원소를 반드시 포함할 때 얻을 수 있는 최대 부분 수열 합을 의미합니다.

풀이 과정은 다음과 같습니다.

  • ret := -inf (최종 결과값을 음의 무한대로 초기화)
  • dp 배열을 정의하고 주어진 배열의 값을 그대로 복사
  • 덱 dq를 하나 정의
  • dq의 앞쪽에 v[0]을 삽입
  • n := v의 크기, ret := v[0]
  • i := 1부터 n 미만까지 1씩 증가시키며 아래 과정을 반복:
    • i > k이고 dq의 첫 번째 원소가 dp[i - k - 1]과 같다면, dq의 앞 원소를 제거 (윈도우 범위를 벗어난 값 삭제)
    • dp[i] := max(dp[i], dq가 비어 있으면 dp[i] + 0, 아니면 dp[i] + dq.front())
    • dq가 비어 있지 않고 dq의 마지막 원소가 dp[i]보다 작은 동안 dq의 뒤 원소를 제거 (덱 내부의 단조 감소 성질 유지)
    • dq의 뒤에 dp[i]를 삽입
    • ret := max(ret, dp[i])
  • 반복이 끝나면 ret을 반환

핵심 아이디어는 덱을 활용해 현재 인덱스에서 거리 k 이내에 있는 이전 dp 값들 중 최댓값을 상수 시간에 조회하는 것입니다. 이를 통해 전체 탐색 시간을 O(n × k)에서 O(n)으로 줄일 수 있습니다.

아래 예제 코드를 통해 더 자세히 이해해 보겠습니다.

예제 코드

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 10;
class Solution {
    public:
    int constrainedSubsetSum(vector<int>& v, int k) {
        int ret = -inf;
        vector<int> dp(v.begin(), v.end());
        deque<int> dq;
        dq.push_front(v[0]);
        int n = v.size();
        ret = v[0];
        for (int i = 1; i < n; i++) {
            if (i > k && dq.front() == dp[i - k - 1])
            dq.pop_front();
            dp[i] = max(dp[i], dq.empty() ? dp[i] + 0 : dp[i] +
            dq.front());
            while (!dq.empty() && dq.back() < dp[i])
            dq.pop_back();
            dq.push_back(dp[i]);
            ret = max(ret, dp[i]);
        }
        return ret;
    }
};
main(){
    Solution ob;
    vector<int> v = {10,2,-9,5,19};
    cout << (ob.constrainedSubsetSum(v, 2));
}

입력

{10,2,-9,5,19}, 2

출력

36