Given an array, a window must be chosen such that this component (sum(a[i] + a[i+1] + a[i+2] ... a[j])* (j-i+1) is maximized where i and j are indices and i<j and the component value must be equal or less than the threshold . (sum(a[i] + a[i+1] + a[i+2] ... a[j])* (j-i+1) <= threshold).
How we can solve this question optimally? Aim is to find the closest value that is less than or equal to threshold.
One example of the problem:
Constraints:
N<=10^5
Threshold<=10^5
A[i]<=10^5
Input N: 8 Arr[]: [2,-3,-4,5,5,6,7,8] Threshold = 20
Output: One possible answer 20
Explanation of output Index:[3, 4] = (5+5)*2 = 20 <= 20 (threshold) and it is the maximum value we can get.
what is the limits of inputs ?what is the upper values of N and threshold ?
I think this should work, first of all, note that we've to find max (prefixsum[j]-prefixsum[i])*(j-i) which is <= threshold, for length of subarray up to sqrt(threshold*log(n)) you can brute-force,now suppose you're at an index i and you've to find an optimal length of size >sqrt(threshold*log(n)) such that (pre[j]-pre[i])*(len)<=threshold, then note that you only care about those j's whose prefixsum value fall in [pre[i],pre[i]+sqrt(threshold/log(n))] and j>i+sqrt(threshold*log(n)), you can use binary search to find the optimal j for each value. This will lead to N *sqrt(threshold*logn) solution which might pass
but in the test case there are negative numbers in the array which mean that prefix sum will not be in increasing values ,is your approach handle this case?
It can be handled easily,In this I assumed threshold >=0 ,Note that if there is a subsegment with sum=0,( i.e. pre[i]=pre[j] for some i!=j) , then clearly our desired answer cant be negative, note that if answer is negative then it must be >= greatest negative number, also let l be the best closest sum found until now by brute force,we are only interested if l<0 , instead of binary searching from [pre[i],pre[i]+sqrt(th/logn)] you can bin search from [pre[i]-l/(sqrt(th*logn),pre[i]+sqrt(th/logn)]. this will lead to a (N^2/sqrt(th*logn)+nsqrt(th*logn)) at worst, we should brute force it upto sqrt(max(n,th)logn) instead of sqrt(th*logn) to make it nsqrt(max(th,n)logn). (Sorry I dont know LATEX)