Maximum Sum Subarray Sum upto k
Given an array nums and a target value k, find the maximum sum of a subarray that sums less than or equal to k. If there isn't one, return 0 instead.
Note:
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range.
Example 1:
Input: nums =[1, -1, 5, -2, 3], k = 4 Output: 4 Explanation: The subarray[1, -1, 5, -2]sums to 3 and is closest <= k.
Example 2:
Input: nums =[3, -1, 2, 7], k = 5 Output: 4 Explanation: The subarray[3, -1, 2]sums to 4 and is closest <= 5.
Follow Up:
Can you do it in O(n) time?
Can you do it in O(n) time?
----
Intuition
Sub array sum => preprocess input to get range sum in const time => create prefix sum
Sum from i to j = prefix[j] - prefix[i - 1], length of subarray = j - 1
Problem reduces to Max (prefix[j] - prefix[i - 1]) such that prefix[j] - prefix[i] <= k
Instead of brute force, we can lookup complement prefix[index] - k from Tree Set
If such complement exists, check if its potentially greater than previous answer
---
Time - O(N Log N)
Space - O(N)
---
Related problems
325-maximum-size-subarray-sum-equals-k
---
Intuition
Sub array sum => preprocess input to get range sum in const time => create prefix sum
Sum from i to j = prefix[j] - prefix[i - 1], length of subarray = j - 1
Problem reduces to Max (prefix[j] - prefix[i - 1]) such that prefix[j] - prefix[i] <= k
Instead of brute force, we can lookup complement prefix[index] - k from Tree Set
If such complement exists, check if its potentially greater than previous answer
---
Time - O(N Log N)
Space - O(N)
---
Related problems
325-maximum-size-subarray-sum-equals-k
---
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| public class Solution { | |
| /** | |
| * @param nums: an array | |
| * @param k: a target value | |
| * @return: the maximum sum of a subarray that is less than k | |
| */ | |
| public int maxSubArrayLen(int[] nums, int k) { | |
| // Current running sum | |
| int sum = 0; | |
| TreeSet<Integer> prefix = new TreeSet<Integer>(); | |
| prefix.add(0); | |
| int ans = Integer.MIN_VALUE; | |
| for (int i= 0 ; i < nums.length ; i++) { | |
| sum += nums[i]; | |
| Integer gap = prefix.ceiling(sum - k); | |
| if (gap != null) { | |
| ans = Math.max(ans, sum - gap); | |
| } | |
| prefix.add(sum); | |
| } | |
| return ans; | |
| } | |
| } |
