넘치게 채우기
[LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays 본문
[LeetCode] 689. Maximum Sum of 3 Non-Overlapping Subarrays
riveroverflow 2024. 12. 28. 16:02https://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;
}
};
'PS > LeetCode' 카테고리의 다른 글
[LeetCode] 983. Minimum Cost For Tickets (0) | 2024.12.31 |
---|---|
[LeetCode] 1639. Number of Ways to Form a Target String Given a Dictionary (0) | 2024.12.29 |
[LeetCode] 1014. Best Sightseeing Pair (0) | 2024.12.27 |
[LeetCode] 494. Target Sum (0) | 2024.12.26 |
[LeetCode] 3203. Find Minimum Diameter After Merging Two Trees (0) | 2024.12.24 |