Largest Contiguous Problem for Range

general
1

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

2

Kadane’s Algorithm:

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 : Largest Sum Contiguous Subarray (Kadane's Algorithm) - GeeksforGeeks