refer to: https://www.algoexpert.io/questions/Max%20Subset%20Sum%20No%20Adjacent
1. 题目描述
给定一个只包含正整数的数组，返回子集的最大和，子集包含的元素之间必须是非临界的。
2. 分析
使用动态规划，创建一个maxSum的数组，maxSum[i]代表当前索引下的Max Subset Sum No adjacent 的值， maxSum[0] = array[0]; maxSum[1] = Max(array[0], array[1]); maxSum[i] = Max(maxSum[i-2] + array[i], array[i-1]) when i > = 2;
if array.length == 0, return 0;
if array.length == 1, return array[0];
if array.length == 2, return Max(array[0], array[1])
else, return maxSum[i] = Max(maxSum[i-2] + array[i], array[i-1]), i > = 2;
3. 代码
O(N) time | O(N) space
import java.util.*; class Program { public static int maxSubsetSumNoAdjacent(int[] array) { if(array.length == 0){ return 0; }else if(array.length == 1){ return array[0]; } int[] maxSum = array.clone(); maxSum[1] = Math.max(maxSum[0], maxSum[1]); for(int i = 2; i < array.length; i++ ){ maxSum[i] = Math.max(maxSum[i-1], maxSum[i-2] + array[i]); } return maxSum[array.length -1]; } }
省空间， O(N) time | O(1) space
由于我们每次更新当前索引下的maxSum的时候只考虑了previous two elements of current element, 我们可以只存储这两个元素，并对它们进行实时更新。
import java.util.*; class Program { public static int maxSubsetSumNoAdjacent(int[] array) { if(array.length == 0){ return 0; }else if(array.length == 1){ return array[0]; } int first = array[0]; int second = Math.max(array[0], array[1]); for(int i = 2; i < array.length; i++ ){ int curr = Math.max(second, first + array[i]); first = second; second = curr; } return second; } }
原文：https://www.cnblogs.com/LilyLiya/p/14261951.html