Find consecutive range in a given list with limit

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

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.

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)); // updated here
            }

            int total = maxB + totalA * numberOfElements;

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

        numberOfElements++;

    } while(found && numberOfElements <= a.size());

    return max;
}

(more test cases can be helpful for further debugging)

I think the main obstacle there is how to efficiently track maximum over sliding window.

Easy optimization in this respect without diving into dynamic programming is to make use of MaxHeap. In java it is implemented as PriorityQueue.

Please consider following code.

    private int findMaxRange(List<Long> listA, List<Long> listB, long limit) {
        int maxRange = 0;
        while (maxRange < listA.size() && isRangePossible(listA, listB, limit, maxRange+1)) {
            maxRange++;
        }
        return maxRange;
    }

    private boolean isRangePossible(List<Long> listA, List<Long> listB, long limit, int rangeSize) {

        //calculate initial values of max and sum
        PriorityQueue<Long> maxHeap = new PriorityQueue<>(rangeSize, Comparator.reverseOrder());
        listB.stream().limit(rangeSize).forEach(maxHeap::add);
        Long max = maxHeap.peek();
        Long sum = listA.stream().limit(rangeSize).mapToLong(i->i).sum();

        //iterate with sliding window
        for (int i = 0; i < listA.size() - rangeSize; i++) {
            if (isConditionMet(max, sum, rangeSize, limit)) {
                return true;
            }

            sum = sum + listA.get(i+rangeSize) - listA.get(i);

            maxHeap.remove(listB.get(i));
            maxHeap.add(listB.get(i+rangeSize));
            max = maxHeap.peek();
        }

        return isConditionMet(max, sum, rangeSize, limit);
    }

    private boolean isConditionMet(Long max, Long sum, int rangeSize, long limit) {
        return max + sum * rangeSize < limit;
    }

Also please pay attention to value ranges. Such big values can easily overflow long and may require specialized types like BigInteger. You should also consider how much memory is used by auxiliary datatypes.

The problem here seems to be use of three nested for loops for calculating max and sum for every window.

We can avoid this unnecessary iterations by using calculations of previous iteration in the new iteration with the help of Dynamic programming.

In my solution, I made 2 2d Arrays, one to store max values for each windows and other to store sums for each windows, storing values of previous iterations will greatly reduce the time complexity.

here is the Java code:

import java.util.*;

public class MyClass {
    public static void main(String[] args) {
        System.out.println("Hello, World!");
        
        List A = Arrays.asList(2,1,3,4,5);
        List B = Arrays.asList(3,6,1,3,4);
        
        
        System.out.println(MyClass.getMax(A, B, 25L));
    }
    
    public static int getMax(List<Integer> A, List<Integer> B, long limit) {
        int n = A.size();
    
        int[][] dp1 = new int[n + 1][n + 1];
        int[][] dp2 = new int[n + 1][n + 1];

        for(int i = 1; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                dp1[i][j] = Math.max(dp1[i - 1][j- 1], B.get(j - 1));
                
                dp2[i][j] = dp2[i - 1][j- 1] + A.get(j - 1);
            }
        }
        
        for(int i = 0; i <= n; i++) {
            for(int j = 0; j <= n; j++) {
                System.out.print("{" + dp1[i][j] + ", " + dp2[i][j] + "}, ");
            }
            System.out.println();            
        }
        
        int kMax = 0;
        
        for(int i = 0; i <= n; i++) {
            for(int j = i; j <= n; j++) {
                if(dp1[i][j] + dp2[i][j] * i <= limit) {
                    kMax = i;
                }
            }
        }
        
        System.out.println("Max K: " + kMax);

        return 0;
    }
}

if you are dependent only on algorithms and not making any app or game, it's not necessary that you have to use java, try using python or c++ (or even c, c#), python is used mostly for algorithms,

or if you need java only then add breakpoints or make the program to print all work it does (ask it to print j, i, k, result variables in console) then you can easily debug.