Find consecutive range in a given list with limit

Question

Find the maximum consecutive elements matching the given condition.

I have a list of numbers called A, another list called B and a limit called Limit.

The task is find the maximum k consecutive elements in A such that they satisfy below condition.

Max(B[i],B[i+1],...B[i+k]) + Sum(A[i], A[i+1], ..., A[i+k]) * k ≤ Limit

Example:

A = [2,1,3,4,5]
B = [3,6,1,3,4]
Limit = 25

Take 2 consecutive elements:
Highest sum occurs with elements in A = 4,5. The corresponding max in B is Max(3,4) = 4.
So value = 4 + (4+5) * 2 = 22. Here 22 ≤ 25, so 2 consecutive is possible

Take 3 consecutive elements:
Taking sum for 1st 3 elements of A = 2,1,3. The corresponding max in B is Max(3,6,1) = 6.
So value = 6 + (2+1+3) * 3 = 24. Here 24 ≤ 25, so 3 consecutive is possible

Take 4 consecutive elements:
Taking sum for 1st 4 elements of A = 2,1,3,4. The corresponding max in B is Max(3,6,1,3) = 6.
So value = 6 + (2+1+3+4) * 4 = 46. Here 46 > 25, so 4 consecutive is not possible

So correct answer to this input is 3.

Constraints:
n (Size of A) is up to 10⁵, A elements up to 10¹⁴, B elements up to 10⁹, Limit up to 10¹⁴.

Here is my code:

public int getMax(List<Integer> A, List<Integer> B, long limit) {
    int result = 0;
    int n = A.size();
    for(int len=1; len<=n; len++) {
        for(int i=0; i<=n-len; i++) {
            int j=i+len-1;
            int max = B.get(i);
            long total = 0;
            for(int k=i; k<=j; k++) {
                total += A.get(k);
                max = Math.max(max, B.get(k));
            }
            total = max + total * len;
            if(total < limit) {
                result = len;
                break;
            }
        }
    }
    return result;
}

This code works for smaller range of inputs. But fails with a time out for larger inputs. How can I reduce time complexity of this code?

Updated:

Updated code based on dratenik answer, but the sample test case mentioned in my post itself is failing. The program is returning 4 instead of 3.

public int getMax(List<Integer> A, List<Integer> B, long limit) {
    int from = 0, to = 0, max = -1;
    int n = A.size();
    for (; from < n;) {
        int total = 0;
        int m = B.get(from); // updated here
        for (int i = from; i < to; i++) {
            total += A.get(i); // updated here
            m = Math.max(m, B.get(i)); // updated here
        }

        total = m + total * (to - from); // updated here

        if (total <= limit && to - from + 1 > max) {
            max = to - from + 1;
        }
        if (total < limit && to < n) { // below target, extend window
            to++;
        } else { // otherwise contract window
            from++;
        }
        if (from > to) {
            to = from;
        }
    }
    return max;
}

Answer 1

Since all the elements of A and B are positive, you can solve this with the usual two-pointer approach to finding a maximum length subarray:

1. Initialize two pointers s and e to the start of the arrays, and then advance e as far as possible without violating the limit. This finds the longest valid subarray that starts at s.
2. While e isn't at the end of the arrays, advance s by one position, and then again advance e as far as possible without violating the limit. This finds the longest valid subarray that starts at every position. This leads to an O(n) algorithm, because e can advance monotonically.
3. Your answer is the longest valid sequence you see.

In order to determine in O(1) whether or not a particular range from s to e is valid, you need to track the cumulative sum of A elements and the current maximum of B elements.

The sum is easy -- just add elements that e passes and subtract elements that s passes.

To track the current maximum of elements in B, you can use the standard sliding-window-maximum algorithm described here: Sliding window maximum in O(n) time. It works just fine with expanding and contracting windows, maintaining O(1) amortized cost per operation.

Here's an O(n) solution in Java. Note that I multiplied the sum of A elements by the length of the sequence, because it's what you seem to intend, even though the formula you wrote multiplies by length-1:

public static int getMax(List<Integer> A, List<Integer> B, long limit) {
    final int size = A.size();
    // a Queue containing indexes of elements that may become max in the window
    // they must be monotonically decreasing
    final int maxQ[] = new int[size];
    int maxQstart = 0, maxQend = 0;
    // current valid window start and end
    int s=0, e = 0;
    int bestLen = 0;
    long windowSum = 0;
    while (s < size && e < size) {
        // calculate longer window max
        long nextMax = maxQstart < maxQend ? B.get(maxQ[maxQstart]) : 0;
        nextMax = Math.max(nextMax, B.get(e));
        long sumPart = (windowSum + A.get(e)) * (e+1-s);
        if (nextMax + sumPart <= limit) {
            // extending the window is valid
            int lastB = B.get(e);
            while (maxQstart < maxQend && B.get(maxQ[maxQend-1]) <= lastB) {
                --maxQend;
            }
            maxQ[maxQend++] = e;
            windowSum += A.get(e);
            ++e;
            if (e-s > bestLen) {
                bestLen = e-s;
            }
        } else if (e > s) {
            // extending the window is invalid.
            // move up the start instead
            windowSum -= A.get(s);
            ++s;
            while(maxQstart < maxQend && maxQ[maxQstart] < s) {
                ++maxQstart;
            }
        } else {
            // we need to move the start up, but the window is empty, so move them both
            ++s;
            ++e;
        }
    }
    return bestLen;
}