Find maximum consecutive elements matching 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.

Constrains:
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 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;
}

CodePudding user response：

Sliding window approach? Slightly pseudocodey version:

int from=0, to=0, max = -1;
for(;from<n;) {
    total = (target expression on elements between from-to inclusive)
    if (total<=target && to-from 1 > max) {max = to-from 1;}
    if (total<target && to<n) { // below target, extend window
        to  ;
    } else { // otherwise contract window
        from  ;
    }
    if (from>to) {to=from;}
}
return max;

The sum could be updated incrementally, but I don't know how to sensibly update the max(B[i],B[i 1],...B[i k]) part when contracting the window, so let's recompute the whole thing at each step.

CodePudding user response：

I tried to use meanigful names to make the code readable. Don't hesitate to ask where it is not clear:

public int getMax(List<Integer> a, List<Integer> b, long limit) {
    
    int max = -1;
    int numberOfElements = 2;
    boolean found;
    
    do{
        found = false;
        for ( int index = 0; index <= a.size() - numberOfElements; index  ) {
            int totalA = 0;
            int maxB = b.get(index);
            for (int i = index; i < index   numberOfElements; i  ) {
                totalA  = a.get(i);
                maxB = Math.max(maxB,b.get(i)); 
            }

            int total = maxB   totalA * numberOfElements;

            if (total <= limit && numberOfElements >= max) {
                max = numberOfElements;
                found = true;
            }
        }

        numberOfElements  ;

    } while(found);

    return max;
}

(more test cases can be helpful for further debugging)