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 = 25Take 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 possibleTake 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 possibleTake 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 possibleSo 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)