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 .
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