Max Subset Sum No Adjacent

• Time : O(n)
• Space : O(n)

#include <vector>
using namespace std;

int helper(vector<int>& dp, vector<int>& A, int p) {
	if(p >= A.size()) return 0;
	if(dp[p] != -1) return dp[p];
	dp[p] = A[p];
	dp[p] = max(dp[p], A[p] + helper(dp, A, p + 2));
	dp[p] = max(dp[p], A[p] + helper(dp, A, p + 3));
	
	return dp[p];
}

int maxSubsetSumNoAdjacent(vector<int> array) {
  vector<int> dp(array.size(), -1);
  return max(helper(dp, array, 0), helper(dp, array, 1));
}