Maximum sum of non consecutive elements (Dynamic Programming)

Question

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.

1. I understand it's an assignment, but why would anyone want this in the real world? 2. In your example, is the max sum 15? 3. One way would be to find the top 3 values and compare their indexes, A simpler way would be: for(i=0;i<array.length-2;i++) for(j=i+2;j<array.length;j++) track max sum and pair of indexes. — iAmOren
– iAmOren, Commented Jul 12, 2020 at 4:24
@iAmOren im practicing an interview question, not an assignment — csguy
– csguy, Commented Jul 12, 2020 at 4:25

גלעד ברקן · Accepted Answer · 2020-07-12 10:49:21Z

1

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]

answered Jul 12, 2020 at 10:49

גלעד ברקן

24k3 gold badges29 silver badges64 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

csguy Over a year ago

appreciate you taking the time to read/understand my q

shiponcs · Accepted Answer · 2020-07-12 05:17:24Z

0

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.

answered Jul 12, 2020 at 5:17

shiponcs

1,70713 silver badges19 bronze badges

Comments

Hikmat Farhat · Accepted Answer · 2020-07-12 08:12:56Z

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:

M[i] includes element i. In this case it cannot include element i-1 so M[i]=A[i]+M[i-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])

Collectives™ on Stack Overflow

Maximum sum of non consecutive elements (Dynamic Programming)

3 Answers 3

1 Comment

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1 Comment

Comments

Comments

Related