arrays - Maximum sum of all subarrays of size k for each k=1..n -

given array of size n, for each k 1 n, find maximum sum of contiguous subarray of size k.

this problem has obvious solution time complexity o(n²) , o(1) space. lua code:

array = {7, 1, 3, 1, 4, 5, 1, 3, 6} n = #array  function maxarray(k)     ksum = 0     = 1, k         ksum = ksum + array[i]     end     max_ksum = ksum     = k + 1, n         add_index =         sub_index = - k         ksum = ksum + array[add_index] - array[sub_index]         max_ksum = math.max(ksum, max_ksum)     end     return max_ksum end  k = 1, n     print(k, maxarray(k)) end 

is there algorithm lower time complexity? example, o(n log n) + additional memory.

related topics:

• kadane's algorithm

below process might you

1) pick first k elements , create self-balancing binary search tree (bst) of size k.

2) run loop = 0 n – k

…..a) maximum element bst, , print it.

…..b) search arr[i] in bst , delete bst.

…..c) insert arr[i+k] bst.

time complexity: time complexity of step 1 o(klogk). time complexity of steps 2(a), 2(b) , 2(c) o(logk). since steps 2(a), 2(b) , 2(c) in loop runs n-k+1 times, time complexity of complete algorithm o(klogk + (n-k+1)*logk) can written o(nlogk).