Maximum Subarray Sum with Constraints
Java
Medium
4 views
Problem Description
Given an array of integers and a target sum, find the maximum possible sum of a contiguous subarray such that the sum does not exceed the target value. If multiple subarrays have the same maximum sum, return the one with the smallest length. If no such subarray exists, return 0.
Input Format
- First line:
Two integers n and target (1 ≤ n ≤ 10^5, -10^9 ≤ target ≤ 10^9)
- Second line:
n space-separated integers (-10^4 ≤ arr[i] ≤ 10^4)
Output Format
- Single integer representing the maximum subarray sum that does not exceed target
- If no valid subarray exists, print 0
Sample Test Case
Input:
```
8 7
1 -3 4 2 -1 2 1 -5
```
Constraints
- Time complexity: O(n log n) or better
- Space complexity: O(n) or better
- Handle edge cases like all negative numbers
- Handle cases where target is negative
Official Solution
```java
import java.util.*;
public class MaximumSubarraySum {
public static int maxSubarraySumWithTarget(int[] nums, int target) {
int n = nums.length;
int maxSum = Integer.MIN_VALUE;
// Use sliding window approach with prefix sums
int[] prefixSum = new int[n + 1];
for (int i = 1; i <= n; i++) {
prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
}
// Use TreeSet to efficiently find the smallest valid prefix sum
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
int result = 0;
for (int i = 1; i <= n; i++) {
// Find the smallest prefix sum such that prefixSum[i] - prefixSum[j] <= target
Integer ceiling = set.ceiling(prefixSum[i] - target);
if (ceiling != null) {
int currentSum = prefixSum[i] - ceiling;
result = Math.max(result, currentSum);
}
set.add(prefixSum[i]);
}
return result;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int target = scanner.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = scanner.nextInt();
}
int result = maxSubarraySumWithTarget(arr, target);
System.out.println(result);
scanner.close();
}
}
```
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!