703423. Maximum sum of subarray less than or equal to x
Easy
Maximum sum of subarray less than or equal to x
Summary
Given an array of integers, find the maximum sum of a subarray that is less than or equal to a given integer x. This problem involves using a sliding window approach and two-pointer technique.
Detailed Explanation
To solve this problem, we can use a sliding window approach with two pointers. Initialize two pointers, left and right, to the start of the array. Calculate the sum of the elements between left and right. If the sum is greater than x, move the left pointer to the right until the sum is less than or equal to x. Update the maximum sum if the current sum is greater.
Here's a step-by-step breakdown:
- Initialize
max_sumto 0, which will store the maximum sum of a subarray that is less than or equal tox. - Initialize
leftandrightpointers to the start of the array. - Calculate the sum of elements between
leftandright. Let's call this sumcurrent_sum. - If
current_sumis greater thanx, move theleftpointer to the right untilcurrent_sumis less than or equal tox. - Update
max_sumifcurrent_sumis greater. - Move the
rightpointer to the right and repeat steps 3-5 untilrightreaches the end of the array. - Return
max_sum.
Time complexity: O(n), where n is the length of the input array. Space complexity: O(1), as we only use a few extra variables.
Optimized Solutions
Java
public int maxSum(int[] arr, int x) {
int max_sum = 0;
int left = 0;
int right = 0;
int current_sum = 0;
while (right < arr.length) {
current_sum += arr[right];
while (current_sum > x && left <= right) {
current_sum -= arr[left];
left++;
}
max_sum = Math.max(max_sum, current_sum);
right++;
}
return max_sum;
}