You are not logged in. Please login at www.codechef.com 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

2★vivek96
533220
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)
link

answered 13 Aug '17, 19:05

afaxnraner's gravatar image

6★afaxnraner
5915
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. http://www.geeksforgeeks.org/divide-and-conquer-maximum-sum-subarray/ .Hope will help you.

link

answered 13 Aug '17, 18:58

droy0528's gravatar image

4★droy0528
956
accept rate: 16%

toggle preview
Preview

Follow this question

By Email:

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

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "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:

×2,719
×847

question asked: 13 Aug '17, 18:22

question was seen: 316 times

last updated: 14 Aug '17, 15:18