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.