Finding the maximum items (consecutive) whose sum is less than a given value?
So, I have an array of all positive natural numbers. I have been given a threshold value. I have to figure out the maximum number of numbers (consecutive) whose sum is less than a given threshold.
For example,
IP: arr = {3,1,2,1}
Threshold = 5
O/P: 3
The maximum size of the input array can be 10 ^ 5.
Basically, I was thinking about an algorithm that calculates the number of elements in subsets of the original array that will sum less than a given threshold. But this will lead to O (N ^ 2) complexity. Can anyone suggest a better algorithm? I am not looking for code and only the algorithm / pseudocode will be fine. Thank!
source to share
public static int maximumSum(int[] array, int t){
int maxSum = 0;
int curSum = 0;
int start = 0;
int end = 0;
while(start < array.length){
if(curSum > maxSum && curSum <= t){
maxSum = curSum;
}
if(curSum <= t && end < array.length){
curSum += array[end];
end += 1;
}
else{
curSum -= array[start];
start+= 1;
}
}
return maxSum;
}
The complexity of this code is O (2 * n), which is essentially O (n). I cannot think of any improvements.
source to share
This will be a little rough, but should point to an O (n) solution
Move the list with two pointers, starting from the beginning, we will call one of them, and the other - a path, since one leads and one route.
keep track of the amount from trail to lead; and the length of the current longest sequence.
As long as the running amount is less than (or equal to) the threshold value, advance the turn signal and adjust the amount by adding the value it now points to. If the sum is still less than (or equal to) the threshold, then trail to lead sequence is possible.
As long as the current amount is greater than the threshold, advance the trail pointer.
Continue until the leading pointer reaches the end.
You will need to fill in the details and implement them carefully, but that seems good enough to me.
source to share
I would try the following:
- Start by summing the elements from the beginning of the array until the threshold is reached. Save this subarak as a temporary result.
- Then remove one element from the beginning of the subarray and try to add new elements on the other side until you reach the threshold again. If the result is greater, replace the next result with a new one.
- Continue to the end of the array.
source to share
Try below ...
public int maximumElem(int[] array,int threshold)
{
int sum = 0;
for(int i=0;i<array.length;i++)
{
sum = sum + array[i]; //sum the values at each index
if(sum >= threshold) //check condition
return (i+1); // if sum is reaching the threshold then return the index
}
}
Hope this helps you ...
Please let me know if you have any further questions ...
source to share