DP #33. Maximum Sum Non Adjacent - mbhushan/dynpro GitHub Wiki
(33). Maximum Sum Non-Adjacent (House Robber Problem).
Given an array of positive numbers, find the maximum sum of a subsequence
with the constraint that no 2 numbers in the sequence should be adjacent in
the array. So 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should
return 15 (sum of 3, 5 and 7).
public int maxSumIter(int [] A) {
int len = A.length;
int incl = A[0];
int excl = 0;
for (int i=1; i<len; i++) {
int tmp = incl;
incl = Math.max(incl, excl+A[i]);
excl = tmp;
}
return Math.max(incl, excl);
}
| Index |
0 |
1 |
2 |
3 |
4 |
5 |
| values |
4 |
1 |
1 |
4 |
2 |
1 |
| Inclusive |
4 |
4 |
5 |
8 |
8 |
9 |
| Exclusive |
0 |
4 |
4 |
5 |
8 |
8 |
Max Sum = max(inclusive, exclusive)
= max(9, 8)
= 9
Max Sum Non-Adjacent
- Time Complexity: O(n)
- Space Complexity: O(1)
Examples:
[2, 5, 3, 1, 7]
max sum: 12
[2, 10, 13, 4, 2, 15, 10]
max sum: 30
[5, 5, 10, 40, 50, 35]
max sum: 80
[5, 5, 10, 100, 10, 5]
max sum: 110
[3, 2, 7, 10]
max sum: 13