×

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

 2 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)  answered 13 Aug '17, 19:05 591●5 accept rate: 22%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×2,719
×847

question asked: 13 Aug '17, 18:22

question was seen: 316 times

last updated: 14 Aug '17, 15:18