The Maximum Sum Non-Adjacent Elements problem requires finding the maximum sum that can be obtained by selecting a subset of non-adjacent elements from an array of positive integers. For example, given the array [1, 2, 3, 4, 5], the maximum sum non-adjacent elements are [1, 3, 5], with a total sum of 9.
Dynamic programming is a useful technique for solving this problem because it allows us to avoid redundant calculations and speed up the computation. We can use dynamic programming to build up a solution from smaller subproblems.
Let’s consider an example with the input array [1, 2, 3, 4, 5]. We can define a function ‘maxSumNonAdjacent‘ that takes the input array and returns the maximum sum of non-adjacent elements. We can use a dynamic programming approach by defining an ‘dp‘ array that keeps track of the maximum sums we can obtain up to the i-th element of the input array.
To fill in the ‘dp‘ array, we can use the following recurrence relation:
dp[i] = max(dp[i-1], dp[i-2] + arr[i])where ‘arr[i]‘ is the i-th element of the input array.
The idea behind this recurrence relation is that we can either include the i-th element in our non-adjacent subset, or we can exclude it. If we include the i-th element, then the maximum sum we can obtain is ‘dp[i-2] + arr[i]‘, since we can’t include adjacent elements. If we exclude the i-th element, then the maximum sum we can obtain is ‘dp[i-1]‘.
To compute the final maximum sum, we simply return ‘dp[n-1]‘, where ‘n‘ is the length of the input array.
Here’s the Java code that implements this dynamic programming approach:
public int maxSumNonAdjacent(int[] arr) {
int n = arr.length;
if (n == 0) {
return 0;
} else if (n == 1) {
return arr[0];
}
int[] dp = new int[n];
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < n; i++) {
dp[i] = Math.max(dp[i-1], dp[i-2] + arr[i]);
}
return dp[n-1];
}For the input array [1, 2, 3, 4, 5], this code would return 9, which is the maximum sum we can obtain by selecting non-adjacent elements [1, 3, 5].