Largest Contiguous Problem for Range

Given N numbers
a(1),a(2)…a(N)

Find the (sum of)contiguous segment having largest sum in range [l,r];
Example
N=5
1 2 3 4 -1 6
therefore Largest contiguous segment sum is 15 for query [1,6] So how can i implement this program.

I tried using segment tree but my query takes log^3 n rather than log n so please help me .

By the way the question is GSS1 of SPOJ

Thanks

Initialize:

``````max_so_far = 0
``````
``````max_ending_here = 0
``````

Loop for each element of the array

(a) max_ending_here = max_ending_here + a[i]

(b) if(max_ending_here < 0)

``````        max_ending_here = 0   (c) if(max_so_far < max_ending_here)
``````
``````        max_so_far = max_ending_here return max_so_far
``````

Explanation:

Simple idea of the Kadane’s algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far

Complexity: O(n)

Read more on it and example here : http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/