Circular Array Subset Sum ā Problem Statement & Solution Guide
Problem Description
Given a circular array of integers weights and an integer capacity, find the maximum sum of a contiguous subarray within the circular array that does not exceed capacity.
Examples
Input
[2, 3, 4, 1], 10
Output
10
Explanation: Step-by-step: Given the array [2, 3, 4, 1] and capacity 10, we consider all possible subarrays, including those that wrap around the end of the array. The maximum sum that does not exceed 10 is 10, which is the sum of the subarray [4, 1, 2, 3].
Input
[3, 1, 2, 3], 6
Output
6
Explanation: Step-by-step: Given the array [3, 1, 2, 3] and capacity 6, we consider all possible subarrays, including those that wrap around the end of the array. The maximum sum that does not exceed 6 is 6, which is the sum of the subarray [1, 2, 3].
Constraints
- 1 <= number of crates <= 10^5
- 1 <= weight of each crate <= 10^6
- 1 <= target storage capacity <= 10^7
Optimal Approach & Strategy
The optimal approach involves using two pointers to track the current window of crates, allowing for a time complexity of O(n). By moving the pointers based on the current total weight, we can efficiently find the maximum total weight of crates that can be stored.
Brute Force Approach
A naive approach would involve checking all possible combinations of crates, resulting in a time complexity of O(nĀ²). This can be improved by using dynamic programming to store intermediate results.
Verified Code Solutions
function circularArraySubsetSum(weights, capacity) {
let maxSum = -Infinity;
for (let i = 0; i < weights.length; i++) {
let currentSum = 0;
for (let j = i; j < weights.length + i; j++) {
currentSum += weights[j % weights.length];
if (currentSum > capacity) break;
maxSum = Math.max(maxSum, currentSum);
}
currentSum = 0;
for (let j = 0; j <= i; j++) {
currentSum += weights[j % weights.length];
if (currentSum > capacity) break;
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}class Solution {
public int circularArraySubsetSum(int[] weights, int capacity) {
int maxSum = Integer.MIN_VALUE;
for (int i = 0; i < weights.length; i++) {
int currentSum = 0;
for (int j = i; j < weights.length; j++) {
currentSum += weights[j];
if (currentSum > capacity) {
break;
}
maxSum = Math.max(maxSum, currentSum);
if (j > 0) {
currentSum -= weights[i];
maxSum = Math.max(maxSum, currentSum);
}
}
}
return maxSum;
}
}def circular_array_subset_sum(weights, capacity):
max_sum = float('-inf')
for i in range(len(weights)):
current_sum = 0
for j in range(i, len(weights)):
current_sum += weights[j]
if current_sum > capacity:
break
max_sum = max(max_sum, current_sum)
if j > 0:
current_sum -= weights[i]
max_sum = max(max_sum, current_sum)
return max_sumfunction circularArraySubsetSum(weights, capacity) {
let maxSum = -Infinity;
for (let i = 0; i < weights.length; i++) {
let currentSum = 0;
for (let j = i; j < weights.length + i; j++) {
currentSum += weights[j % weights.length];
if (currentSum > capacity) break;
maxSum = Math.max(maxSum, currentSum);
}
currentSum = 0;
for (let j = 0; j <= i; j++) {
currentSum += weights[j % weights.length];
if (currentSum > capacity) break;
maxSum = Math.max(maxSum, currentSum);
}
}
return maxSum;
}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.