Longest subarray whose sum <= k - EPI

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(, )

Input: An array  and a real number 
Output: A pair of indices , maximizing , subject to 
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 
        
        
6. 
7. for  up to 
    if 
        Use binary search to look for the rightmost element  in  such that . If such an element exists, update  to  if 
        
8. return 

Find the longest subarray whose sum <= k
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.

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 <= k