please explain your approach asked 13 Aug '17, 18:22

This is an answer for the original question: How to find the maximal sum of consecutive elements? Kadane's algorithm solves this one. The main idea behind the algorithm is dynamic programming. Lets define $dp[i]$ as the biggest sum of consecutive elements ending at index $i$. Then the maximal sum in total is $\max(dp[0], dp[1], \dots, dp[n1])$. So we can easily compute the maximal sum if we compute all values of $dp$. For computing $dp[i]$ using recursion. There are two possibilities. Either the largest sum contains only one element, than $dp[i] = A[i]$. Or it contains more elements, lets say $A[j] + \dots + A[i]$. But this means, that $A[j] + \dots + A[i1]$ has to be the biggest sum of consecutive elements ending at index $i1$. (Otherwise, if the biggest sum of consecutive elements ending at index $i1$ would be $A[k] + \dots + A[i1]$, then $A[k] + \dots + A[i]$ would be greater than $A[j] + \dots + A[i]$, which would be a contradiction.) So in this case $dp[i] = dp[i1] + A[i]$. If we combine these two cases, we get $dp[i] = \max(A[i], dp[i] + A[i])$ . With dynamic programming you can effectively compute the array $dp$. And then compute the answer with another loop.
There is one thing that can be optimized. We can combine the two for loops. And if we do this, we can realize that we only need $dp[i1]$ to compute $dp[i]$. So we don't actually need to keep all values in the array. We only need the last one. And so we can simplify the algorithm to:
answered 13 Aug '17, 19:05

Please refer to this article it has detailed explanation with a DIVIDE AND CONQUER APPROACH and with Kadanes Algorithm. http://www.geeksforgeeks.org/divideandconquermaximumsumsubarray/ .Hope will help you. answered 13 Aug '17, 18:58
