Tome Voyage Consolidator 1 — Problem Statement & Solution Guide
Problem Description
You are tasked with optimizing the consolidation of data streams represented by a sequence of integers, where each integer denotes a specific metric value. Given an array metrics of length n and a capacity threshold K, determine the maximum possible sum of a subset of these metrics such that the total sum does not exceed K. The selection process must respect the order of elements in the original sequence, meaning you can only pick elements in their given order, but you are not required to pick contiguous elements. This problem requires an efficient algorithm to navigate the trade-off between maximizing the sum and adhering to the strict capacity constraint.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Tome Voyage Consolidator 1"
WHY DOES IT MATTER?
Subset‑sum DP is a foundational pattern for any problem that asks "can we reach a target using a subset of items?" It appears in budgeting, resource allocation, and capacity planning, making it a go‑to tool for interviewers to gauge a candidate’s ability to convert exponential combinatorics into tractable pseudo‑polynomial solutions.
OPTIMIZATION CHALLENGE
The breakthrough is recognizing that we only need to know *which sums are reachable*, not the exact subsets. This reduces the state space from O(n·K) boolean matrix to a single 1‑D array of size K+1, cutting memory by a factor of n and enabling in‑place updates.
REAL-WORLD CONNECTION
Think of a streaming data pipeline that must batch events without exceeding a memory quota K. Each event’s size is a metric; the pipeline must decide which events to keep in order (preserving timestamps) while maximizing total processed data. The DP mirrors the decision engine that continuously updates which cumulative sizes are feasible.
During the interview, write the DP as a set of reachable sums and update it in‑place. After each element, optionally prune sums that are strictly dominated (e.g., keep only the maximum sum for each reachable value) – but the simple backward loop is usually enough and avoids off‑by‑one bugs.
COMPLEXITY AT A GLANCE
O(n*K)O(K)Core Theory — Why This Approach?
The problem is a classic variant of the Subset‑Sum / 0‑1 Knapsack where each item’s weight equals its value and we must respect the original ordering of the array. A naïve solution would enumerate every possible subsequence (2^n possibilities) and keep the best sum ≤ K, which explodes exponentially and is infeasible for n > 30. The optimal paradigm uses dynamic programming: we maintain a boolean DP table dp[s] that indicates whether a sum s can be achieved using the first i elements. For each metric value v we iterate s from K down to v and set dp[s] = dp[s] || dp[s‑v]. After processing all elements, the largest s with dp[s] true is the answer. This DP runs in O(n·K) time and O(K) space, turning an exponential search into a pseudo‑polynomial algorithm that scales to typical constraints (n up to 10^3‑10^5, K up to 10^5‑10^6). The key insight is that the decision to include or exclude an element depends only on the reachable sums so far, not on the exact composition of the subset, allowing us to compress the state dimension to a single sum axis.
Interview Questions on This Problem
Q1How would you modify the DP if each metric also had a separate cost and you needed to maximize total value while keeping total cost ≤ K?
The problem becomes the classic 0‑1 knapsack where weight = cost and value = metric. We would use a DP array dp[w] storing the maximum value achievable with total cost w, iterating items and updating dp from K down to cost_i: dp[w] = max(dp[w], dp[w‑cost_i] + value_i). The answer is max_{w≤K} dp[w].
Q2Explain how you could solve the same problem when K is as large as 10^9 but n ≤ 30.
When K is huge but n is small, we can use the meet‑in‑the‑middle technique: split the array into two halves, enumerate all subset sums of each half (2^{n/2} each), sort one list, and for each sum in the first list binary‑search the largest complementary sum in the second list such that total ≤ K. This runs in O(2^{n/2} log 2^{n/2}) time and uses O(2^{n/2}) space.
Q3Why does iterating the DP sum dimension backwards (from K down to v) matter in the 0‑1 version?
Iterating backwards ensures that each element is used at most once per iteration. If we iterated forward, dp[s‑v] could have been updated earlier in the same pass, effectively allowing the current element to be counted multiple times, which turns the 0‑1 knapsack into an unbounded knapsack.
Examples
Input
metrics = [3, 1, 4, 1, 5], K = 9
Output
9
Explanation: We evaluate subsets of the sequence [3, 1, 4, 1, 5] that sum to at most 9. The subset [3, 1, 4, 1] sums to 9, which is the maximum possible value not exceeding K. Other combinations like [4, 5] sum to 9 as well, but [3, 1, 4, 1] is a valid subsequence. The maximum sum is 9.
Input
metrics = [10, 20, 30], K = 25
Output
20
Explanation: The possible subsets and their sums are: [10] -> 10, [20] -> 20, [30] -> 30 (exceeds K), [10, 20] -> 30 (exceeds K), [10, 30] -> 40 (exceeds K), [20, 30] -> 50 (exceeds K). The only valid subsets are [10] and [20]. The maximum sum among these is 20.
Input
metrics = [1, 2, 3, 4, 5], K = 100
Output
15
Explanation: Since the sum of all elements (1+2+3+4+5 = 15) is less than K (100), the optimal strategy is to include all elements. The maximum sum is 15.
Input
metrics = [5, 5, 5, 5], K = 12
Output
10
Explanation: Each element is 5. We can pick at most two elements because 5+5=10 <= 12, but 5+5+5=15 > 12. The maximum sum is 10.
Constraints
- 1 <= metrics.length <= 100
- 1 <= metrics[i] <= 1000
- 1 <= K <= 100000
Optimal Approach & Strategy
Use a 1‑D DP array of size K+1, updating reachable sums backwards for each element, then scan for the highest reachable sum.
Brute Force Approach
Enumerate every subsequence (2^n possibilities), compute its sum, and keep the maximum sum ≤ K.
Verified Code Solutions
/**
* @param {number[]} metrics
* @param {number} K
* @return {number}
*/
var maxSubsetSum = function(metrics, K) {
const dp = new Array(K + 1).fill(0);
for (let i = 0; i < metrics.length; i++) {
for (let j = K; j >= metrics[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - metrics[i]] + metrics[i]);
}
}
return dp[K];
};class Solution {
public:
int maxSubsetSum(vector<int>& metrics, int K) {
int n = metrics.size();
vector<int> dp(K + 1, 0);
for (int i = 0; i < n; ++i) {
for (int j = K; j >= metrics[i]; --j) {
dp[j] = max(dp[j], dp[j - metrics[i]] + metrics[i]);
}
}
return dp[K];
}
};class Solution {
public int maxSubsetSum(int[] metrics, int K) {
int[] dp = new int[K + 1];
for (int m : metrics) {
for (int j = K; j >= m; j--) {
dp[j] = Math.max(dp[j], dp[j - m] + m);
}
}
return dp[K];
}
}class Solution:
def maxSubsetSum(self, metrics: List[int], K: int) -> int:
dp = [0] * (K + 1)
for m in metrics:
for j in range(K, m - 1, -1):
dp[j] = max(dp[j], dp[j - m] + m)
return dp[K]/**
* @param {number[]} metrics
* @param {number} K
* @return {number}
*/
var maxSubsetSum = function(metrics, K) {
const dp = new Array(K + 1).fill(0);
for (let i = 0; i < metrics.length; i++) {
for (let j = K; j >= metrics[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - metrics[i]] + metrics[i]);
}
}
return dp[K];
};Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.