algorithm - sum of contiguous subarray modified -

given 1 dimensional array of size n may contain both positive , negative integers , integer k, find sum of contiguous subarray of numbers has largest sum such no element in selected array greater k. k changes provided q queries each containing 1 integer i.e k.

example : let n=5 , q=6 , array [1 2 3 4 5] , queries :

query 1 : k=5 chosen subarray [1,2,3,4,5]. sum of elements = 15.

query 2 : k=4 chosen subarray [1,2,3,4]. sum of elements = 10.

query 3 : k=3 chosen subarray [1,2,3]. sum of elements = 6.

query 4 : k=2 chosen subarray [1,2]. sum of elements = 3.

query 5 : k=1 chosen subarray [1]. sum of elements = 1.

query 6 : k=0 there no element x in array such x <= 0. therefore, answer "no solution".

how answer these queries effieciently ? please 1 ≤ n,q ≤ 5*10^5 , -10^ 9 ≤ ai,k ≤ 10^9

you can solve linearly. here steps :

1. initialize sum=0 , maximum_sum=0
2. loop through index 1 n
   -- if current index value less or equal k add current value sum. if greater make sum=0
   -- if current sum greater maximum_sum, update maximum_sum
3. print maximum_sum

complexity : o(n)