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