algorithm - Finding continuous subsequence that minimizes the average of the rest of the array? -

suppose there's integer array arr[0..n-1]. find subsequence sub[i..j] (i > 0 , j < n - 1) such rest of array has smallest average.

example:

arr[5] = {5,1,7,8,2}; 

remove {7,8}, array becomes {5, 1, 2} has average 2.67 (smallest possible).

i thought modification of longest increasing subsequence couldn't figure out.

thanks,

let's find average value using binary search.

suppose, sum of elements s.

for given x let's check if exist , j such avg of elements except j less or equal x.

to that, let's subtract x elements in arr. need check if exists , j such sum of elements except j less or equal zero. that, lets find sum of elements in current array: s' = s - x * n. want find , j such sum j greater or equal s'. that, let's find subarray larges sum. , can done using elegant jay kadane's algorithm: https://en.wikipedia.org/wiki/maximum_subarray_problem

when terminate binary search? when maximum subarray sum 0 (or close enough).

time complexity: o(n log w), w - presicion of binary search.