CODEWITHSUNDEEP
algorithmdynamic-programming
csguy
csguy

Reputation: 1484

Maximum sum of non consecutive elements (Dynamic Programming)

Given an array of positive integers, what's the most efficient algorithm to find non-consecutive elements from this array which, when added together, produce the maximum sum?

The dynamic programming solution is to use an auxiliary array maxSum holding the max sum up until that particular index. We start by setting the first 2 indices of the array, and fill the rest of the array with max(array[i]+maxSum[i-2], maxSum[i-1]).

I understand that we cannot add adjacent elements, but I am struggling to understand how the above solution takes into consideration that it is possible for the the previous element in maxSum[i] to not be the result of summing with array[i].

For example:

index:  0 1 2  3 4

array:  3 5 -7 8 10

maxSum: 3 5 5  _

We see that maxSum[2] is not a result of summing with array[2].

To find maxSum[3] = max(array[3]+maxSum[1], maxSum[2]), but why don't we consider maxSum[2] + array[3]? Since it is possible for maxSum[2] to not consist of the adjacent array[2] value.

Upvotes: 1

Views: 1583

Answers (3)

גלעד ברקן
גלעד ברקן

Reputation: 23955

how does the above solution take into consideration that it is possible for the previous element in maxSum[i] to not be the result of summing with array[i]?

Simply. If the previous element in maxSum[i] is not to be included in the result of summing with array[i], we can look at maxSum[i - 2]. We do this explicitly in

array[i]+maxSum[i-2]

we compare that against the option of not including array[i], which is

maxSum[i-1]

Upvotes: 1

Hikmat Farhat
Hikmat Farhat

Reputation: 592

I am assuming you need an explanation of the reasoning, here it is.

Let M[i] be the maximum sum we can obtain by including the first i elements of the array A (with the condition that no two are consecutive). There are two possibilities:

  1. M[i] includes element i. In this case it cannot include element i-1 so M[i]=A[i]+M[i-2]

  2. M[i] does not include element i. In this case M[i]=M[i-1].

Since we don't know if it actually includes i or not we compute both cases and choose the maximum between the two thus

M[i]=max(M[i-1],A[i]+M[i-2])

Upvotes: 0

shiponcs
shiponcs

Reputation: 1687

First all, you might not understand the procedure completely:

  • For each index i, maxSum represents the max of (sum by including i-th element, sum by excluding i-th element)
  • maxSum[3] = max(array[3]+maxSum[1], maxSum[2]), because array[3]+maxSum[1] represents the sum if array[3] is taken, and maxSum[2] if array[3] is excluded.

Upvotes: 0

Related Questions