 # how to find sum of consective array elements equals to n?

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, dp, \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 = A // 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
for i = 1 to n-1:
last_dp = max(A[i], last_dp + A[i])
answer = max(answer, last_dp)``````
2 Likes