Problem Description
Given an array arr[] of positive numbers, The task is to find the maximum sum of a subsequence such that no 2 numbers in the sequence should be adjacent in the array.
Solution
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution
{
public int FindMaxSum(int arr[], int n)
{
//Edge cases
if(n == 0) return 0;
if(n == 1) return arr[0];
int[] dp = new int[n];
//Single element, max is itself
dp[0] = arr[0];
//If N=2, max is the max out of those two elements since we cannot select both as they are adjacent
dp[1] = Math.max(arr[0], arr[1]);
//Set current max
int maxSum = dp[1];
//Include other numbers one by one and check for max
for(int i=2; i<n; i++){
//select current
//So, we cannot select previous number
//We can add max that we found for elements from index 0 to i-2 -> which is dp[i-2]
int option1 = arr[i] + dp[i-2];
//don't select current
//So the max will be the max for elements from index 0 to i-1 -> which is dp[i-1]
int option2 = dp[i-1];
dp[i] = Math.max(option1, option2);
maxSum = Math.max(maxSum, dp[i]);
}
return maxSum;
}
}