You are not logged in. Please login at to post your questions!


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

please explain your approach

asked 13 Aug '17, 18:22

vivek96's gravatar image

accept rate: 8%

edited 13 Aug '17, 19:07

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

afaxnraner's gravatar image

accept rate: 22%

edited 14 Aug '17, 15:18

Please refer to this article it has detailed explanation with a DIVIDE AND CONQUER APPROACH and with Kadanes Algorithm. .Hope will help you.


answered 13 Aug '17, 18:58

droy0528's gravatar image

accept rate: 16%

toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "title")
  • 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:


question asked: 13 Aug '17, 18:22

question was seen: 316 times

last updated: 14 Aug '17, 15:18