please explain your approach
Please refer to this article it has detailed explanation with a DIVIDE AND CONQUER APPROACH and with Kadanes Algorithm. http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/ .Hope will help you.
1 Like
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[n-1]). 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[i-1] has to be the biggest sum of consecutive elements ending at index i-1. (Otherwise, if the biggest sum of consecutive elements ending at index i-1 would be A[k] + \dots + A[i-1], 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[i-1] + 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.
dp = array of size n
dp[0] = A[0] // base case
for i = 1 to n-1:
dp[i] = max(A[i], dp[i] + A[i])
answer = 0
for i = 0 to n-1:
answer = max(answer, dp[i])
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[i-1] 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:
answer = last_dp = A[0]
for i = 1 to n-1:
last_dp = max(A[i], last_dp + A[i])
answer = max(answer, last_dp)
2 Likes