Largest Contiguous Problem for Range

Given N numbers

Find the (sum of)contiguous segment having largest sum in range [l,r];
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


Kadane’s Algorithm:


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


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 :