넘치게 채우기

[LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays 본문

PS/LeetCode

[LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays

riveroverflow 2024. 12. 28. 16:02
728x90
반응형

https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/description/

leetcode - Maximum Sum of 3 Non-Overlapping Subarrays

문제 유형: 슬라이딩 윈도우, 부분합, 다이나믹 프로그래밍

문제 난이도: Hard

 

문제

Given an integer array nums and an integer k, find three non-overlapping subarrays of length k with maximum sum and return them.

Return the result as a list of indices representing the starting position of each interval (0-indexed). If there are multiple answers, return the lexicographically smallest one.

 

 

풀이

처음에는 dp[idx][streak] = {이전 인덱스, 부분합}으로 문제를 풀어서 부분합 배열을 거꾸로 순회하면서 현재 i보다 큰 인덱스중에서 가장 큰 이전 streak에 연결시키는 방법으로 접근했다.

그 뒤, dp[i][2]에서 가장 큰 i를 골라서 그 i부터의 trace를 반환했다.

 

그러나, 더 간단한 접근이 있다.

왼쪽에서 가장 큰 부분합과, 오른쪽에서 가장 큰 부분합을 찾아서 자신과 더해 나온 가장 크게 나오게 하면 쉽고 더 빠르게 찾을 수 있다.

즉, left배열과 right배열을 만들어서 left[i] = [0:i]까지중 가장 큰 부분합을 가진 인덱스, right[l]는 [l:n-k]에서 가장 큰 부분합을 가진 인덱스로 저장시키면 쉽게 세 출발지를 찾아낼 수 있다.

 

공통점은 각 부분배열의 합을 미리 슬라이딩 윈도우로 구해놔야 한다는 것이다.

 

코드

C++

1 - dp를 이용해서 LIS처럼 만들기

class Solution {
public:
    vector<int> trace(int start_idx, vector<vector<pair<int, int>>>& dp) {
        int i = start_idx;
        int j = 2;
        vector<int> res;
        while(i != -1) {
            res.push_back(i);
            i = dp[i][j].first;
            j--;
        }
        return res;
    }
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int sum = 0;
        int n = nums.size();
        int m = n-k+1;
        vector<int> sums (n-k+1, 0);
        for(int i = n-1; i >= m; --i) {
            sum += nums[i];
        }

        for(int i = n-k; i >= 0; --i) {
            sum += nums[i];
            sums[i] = sum;
            sum -= nums[i+k-1];
        }

        vector<vector<pair<int, int>>> dp(m, vector<pair<int, int>>(3)); // dp[startidx, stack] = (nextIdx, sum)
        for(int i = m-1; i >= 0; --i) {
            dp[i][0] = {-1, sums[i]};
            int largest_0 = -1;
            int largest_1 = -1;
            int nextIdx_0 = -1;
            int nextIdx_1 = -1;
            for(int j = m-1; j >= i+k; --j) {
                if(dp[j][0].second >= largest_0) {
                    largest_0 = dp[j][0].second;
                    nextIdx_0 = j;
                }
                if(dp[j][1].second >= largest_1) {
                    largest_1 = dp[j][1].second;
                    nextIdx_1 = j;
                }
            }
            if(nextIdx_0 != -1) {
                dp[i][1] = {nextIdx_0, largest_0 + sums[i]};
            }
            if(nextIdx_1 != -1) {
                dp[i][2] = {nextIdx_1, largest_1 + sums[i]};
            }
        }

        int maxNum = -1;
        int start_idx = -1;
        for(int i = 0; i < m; ++i) {
            if(maxNum < dp[i][2].second) {
                maxNum = dp[i][2].second;
                start_idx = i;
            }
        }

        return trace(start_idx, dp);
    }
};

/*
 0  1  2  3  4  5  6  7
 1  2  1  2  6  7  5  1
 3  3  3  8 13 12  6
 */

 

2 - 최적화된 풀이(왼쪽 짝과 오른쪽 짝 찾기)

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
        int n = nums.size();

        vector<int> sums(n - k + 1, 0);
        int windowSum = 0;
        for (int i = 0; i < k; i++) {
            windowSum += nums[i];
        }
        sums[0] = windowSum;
        for (int i = k; i < n; i++) {
            windowSum += nums[i] - nums[i - k];
            sums[i - k + 1] = windowSum;
        }
        
        vector<int> left(n - k + 1);
        int best = 0;
        for (int i = 0; i < n - k + 1; i++) {
            if (sums[i] > sums[best]) {
                best = i;
            }
            left[i] = best;
        }

        vector<int> right(n - k + 1);
        best = n - k;
        for (int i = n - k; i >= 0; i--) {
            if (sums[i] >= sums[best]) {
                best = i;
            }
            right[i] = best;
        }
        int maxTotal = INT_MIN;
        vector<int> ans(3, -1);
        for (int j = k; j <= n - 2 * k; j++) {
            int i = left[j - k];
            int l = right[j + k];
            int total = sums[i] + sums[j] + sums[l];
            if (total > maxTotal) {
                maxTotal = total;
                ans = {i, j, l};
            }
        }
        return ans;
    }
};
728x90
반응형