Leetcode Problem:
Summary
- Given an integer array and an integer k, find three non-overlapping subarrays of length k with maximum sum and return their starting indices.
Approach
- Dynamic programming and depth-first search are used to find the maximum possible sum of subarrays and then reconstruct the path to find the starting indices.
Complexity
- O(n * 4^k) where n is the size of the input array, as the dynamic programming function is called for each possible subarray and for each possible number of subarrays remaining.
Explanation
- The solution first calculates the sum of all possible k-length subarrays using a sliding window approach
- Then, it uses dynamic programming to find the maximum possible sum of subarrays
- The dynamic programming function tries taking the current subarray vs skipping it and returns the maximum result
- Finally, the solution uses depth-first search to reconstruct the path to find the starting indices of the subarrays.
Solution Code:
class Solution {
public:
vector maxSumOfThreeSubarrays(vector& nums, int k) {
// Number of possible subarray starting positions
int n = nums.size() - k + 1;
// Calculate sum of all possible k-length subarrays
vector sums(n);
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
sums[0] = windowSum;
// Sliding window to calculate remaining sums
for (int i = k; i < nums.size(); i++) {
windowSum = windowSum - nums[i - k] + nums[i];
sums[i - k + 1] = windowSum;
}
// memo[i][j]: max sum possible starting from index i with j subarrays
// remaining
vector> memo(n, vector(4, -1));
vector indices;
// First find optimal sum using DP
dp(sums, k, 0, 3, memo);
// Then reconstruct the path to find indices
dfs(sums, k, 0, 3, memo, indices);
return indices;
}
private:
// DP function to find maximum possible sum
int dp(vector& sums, int k, int idx, int rem,
vector>& memo) {
if (rem == 0) return 0;
if (idx >= sums.size()) {
return rem > 0 ? INT_MIN : 0;
}
if (memo[idx][rem] != -1) {
return memo[idx][rem];
}
// Try taking current subarray vs skipping it
int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
int skipCurrent = dp(sums, k, idx + 1, rem, memo);
memo[idx][rem] = max(withCurrent, skipCurrent);
return memo[idx][rem];
}
// DFS to reconstruct the solution path
void dfs(vector& sums, int k, int idx, int rem,
vector>& memo, vector& indices) {
if (rem == 0) return;
if (idx >= sums.size()) return;
int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
int skipCurrent = dp(sums, k, idx + 1, rem, memo);
// Choose path that gave optimal result in DP
if (withCurrent >= skipCurrent) { // Take current subarray
indices.push_back(idx);
dfs(sums, k, idx + k, rem - 1, memo, indices);
} else { // Skip current subarray
dfs(sums, k, idx + 1, rem, memo, indices);
}
}
};
class Solution {
public:
vector maxSumOfThreeSubarrays(vector& nums, int k) {
// Number of possible subarray starting positions
int n = nums.size() - k + 1;
// Calculate sum of all possible k-length subarrays
vector sums(n);
int windowSum = 0;
for (int i = 0; i < k; i++) {
windowSum += nums[i];
}
sums[0] = windowSum;
// Sliding window to calculate remaining sums
for (int i = k; i < nums.size(); i++) {
windowSum = windowSum - nums[i - k] + nums[i];
sums[i - k + 1] = windowSum;
}
// memo[i][j]: max sum possible starting from index i with j subarrays
// remaining
vector> memo(n, vector(4, -1));
vector indices;
// First find optimal sum using DP
dp(sums, k, 0, 3, memo);
// Then reconstruct the path to find indices
dfs(sums, k, 0, 3, memo, indices);
return indices;
}
private:
// DP function to find maximum possible sum
int dp(vector& sums, int k, int idx, int rem,
vector>& memo) {
if (rem == 0) return 0;
if (idx >= sums.size()) {
return rem > 0 ? INT_MIN : 0;
}
if (memo[idx][rem] != -1) {
return memo[idx][rem];
}
// Try taking current subarray vs skipping it
int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
int skipCurrent = dp(sums, k, idx + 1, rem, memo);
memo[idx][rem] = max(withCurrent, skipCurrent);
return memo[idx][rem];
}
// DFS to reconstruct the solution path
void dfs(vector& sums, int k, int idx, int rem,
vector>& memo, vector& indices) {
if (rem == 0) return;
if (idx >= sums.size()) return;
int withCurrent = sums[idx] + dp(sums, k, idx + k, rem - 1, memo);
int skipCurrent = dp(sums, k, idx + 1, rem, memo);
// Choose path that gave optimal result in DP
if (withCurrent >= skipCurrent) { // Take current subarray
indices.push_back(idx);
dfs(sums, k, idx + k, rem - 1, memo, indices);
} else { // Skip current subarray
dfs(sums, k, idx + 1, rem, memo, indices);
}
}
};
'알고리즘' 카테고리의 다른 글
| Count Ways To Build Good Strings (0) | 2025.03.03 |
|---|---|
| Number of Ways to Form a Target String Given a Dictionary (0) | 2025.03.03 |
| Best Sightseeing Pair (0) | 2025.03.03 |
| Target Sum (0) | 2025.03.03 |
| Find Largest Value in Each Tree Row (0) | 2025.03.03 |
짬뽕얼큰하게
