Longest subarray whose sum <= k
Longest subarray whose sum
Given an array
of
numbers and a key
, find the longest subarray of
for which the subarray sum is less than or equal to
.
In the following we describe an algorithm with time complexity
.
Algorithm LONGESTSUBARRAY(
,
)
Longest_subarray_k_improved.cpp LongestSubarrayK.java
Longest subarray whose sum
Given an array
In the following we describe an algorithm with time complexity
Algorithm LONGESTSUBARRAY(
Input: An array
and a real number 
Output: A pair of indices
, maximizing
, subject to ![\sum_{t = i}^j A[t] \leq k \sum_{t = i}^j A[t] \leq k](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tD4t_Zgyl4HSN-0ORXw_5ctPh0fR9P2BFLmiK6aE4urniHtZZ7UOFsjAmNqqehWrg89ZyacmqQu6xrW242nXNZ8DkTXb5KZkE3ZE2leK85LCvgVseeFxR0uwcGNBE70o-Sxbls4WuymnZ8vkmbkwPqmyJtp56Ri1hGl1H9iIZu7TLGog=s0-d)
1. Compute the array
of partial sums, where
is the prefix sum of the first
numbers in
.
.
2.
3.
4.
5. for
down to 0
if![S[i] < {\rm smallest} S[i] < {\rm smallest}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_tNz4OR5g_gjyIf5Apd12h86pUANKBrnS_EYdoIf220f4GM3KObZHZffez64qMiepyRjsqYZChOvgwNwnkvZMo5ibwHUG1-juyP-wWJ_jxg9GGIMKhcVzW3RCFmRJb0Ebvy7C6jxYjjZ39UaWENQNLBlh-YsZe-8_Zoig=s0-d)
![M \leftarrow M \cup \{(S[i], i)\} M \leftarrow M \cup \{(S[i], i)\}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_sPSLz81EgRYUM34X3pR-gDrOHlEDuePFwLD8Nj4_VliaRPRsJtPsN1mXX5_5RG_uTsXxPvNP0mCZLkTXGrzK6qLV-WGmiH30hqmFIj6lCBBFEkFAP81zSWInzN7q_Y4S9J_QoeyIsmIuHpLpvTPkAVjb-oSXVmRMNKhkjN2B6RiVx42605grojvrw=s0-d)
![{\rm smallest} \leftarrow S[i] {\rm smallest} \leftarrow S[i]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_vc9hunLMv5E-8OZM9wd4F6G0jwlUpDnvTq8pI_GJ4o-1j-32gT7LHhoc-GiopB_S4DMepHmUOnj1s5C86vSQNLQiNtL-Zr1nxslU8KwkMt-bbamyb7PxOluCrcheUuGWMDvXuR4_4uYGzNIj1yCKfGWDYuPsTKZRm8IF6bT34h4Fp6=s0-d)
6.
7. for
up to 
if![S[i] > {\rm current} S[i] > {\rm current}](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_srE_xN214KQ902CmzGNFzLItMK-q5rcT6NeafaxKDcriYtUu7Cqc7MPpm3gZTqhJ2vbf5PZlKn9m1BHSep34J8bcz_lcwDgXrz1fXmO10D2CPw0e2EvBFyVGkzzKhuoVjoNtWn9lKn8jdBGf8W9goofvkJf9DiBGXh=s0-d)
Use binary search to look for the rightmost element
in
such that
. If such an element exists, update
to
if 
![{\rm current} \leftarrow S[i] {\rm current} \leftarrow S[i]](https://lh3.googleusercontent.com/blogger_img_proxy/AEn0k_u94_3Q-u-kpHSZIZyJjcjSACQUQqNQaY0tsrNzcrSn_7VtaP5EdiZKB-pAKQ8KuA5VCKTmpt0N0UTYLiHbeTu-P23ojP6tdQiNpfcVjCQulDFZt4THErSsotnbytEe6mtncdGxy2p6qXEgAtkOKmNU4IrAokNtvZS7oQ4yOBFUL-Xr=s0-d)
8. return
Find the longest subarray whose sum <= kOutput: A pair of indices
1. Compute the array
2.
3.
4.
5. for
if
6.
7. for
if
Use binary search to look for the rightmost element
8. return
Longest_subarray_k_improved.cpp LongestSubarrayK.java
public static Pair<Integer, Integer> findLongestSubarrayLessEqualK(
List<Integer> A, int k) {
// Build the prefix sum according to A.
List<Integer> prefixSum = new ArrayList<>();
int sum = 0;
for (int a : A) {
sum += a;
prefixSum.add(sum);
}
List<Integer> minPrefixSum = new ArrayList<>(prefixSum);
for (int i = minPrefixSum.size() - 2; i >= 0; --i) {
minPrefixSum.set(i,
Math.min(minPrefixSum.get(i), minPrefixSum.get(i + 1)));
}
Pair<Integer, Integer> arrIdx = new Pair<>(0,
upperBound2(minPrefixSum, k) - 1);
for (int i = 0; i < prefixSum.size(); ++i) {
int idx = upperBound2(minPrefixSum, k + prefixSum.get(i)) - 1;
if (idx - i - 1 > arrIdx.getSecond() - arrIdx.getFirst()) {
arrIdx = new Pair<>(i + 1, idx);
}
}
return arrIdx;
}
Correctness of the Algorithm
The key is to observe the following two facts.
Claim: (1) If two indices
satisfies that
, then
cannot appear in an optimum solution; (2) If two indices
satisfies that
, then
cannot appear in an optimum solution.
Proof: For any index
,
, note that the subarray sum of
is less than the subarray sum of
, and the length of the subarray $A[i..r']$ is greater than the length of the subarray
(although both length might be negative, but the statement still holds). Therefore,
is preferable over
. This is also the reason why we compute the strictly increasing sequence of
.
The second statement follows a similar reasoning.
Claim: (1) If two indices
Proof: For any index
The second statement follows a similar reasoning.
Time Complexity and Space Complexity
Step 1, computing the prefix sums, takes
time. Step 4, computing the array
, takes
time. Step 7 takes
time as each iteration takes
time.
Please read full article from Longest subarray whose sum <= kStep 1, computing the prefix sums, takes