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

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 = last_dp = A