Cooler than KnapSack

Familiarizing oneself with Design and Analysis of Algorithms this semester, one of the problems my professor keeps talking about is the KnapSack Problem.

In the presented problem we have N items where each item has some profit and weight associated with it and also given a bag with capacity W, and profits associated with them being P. The task is to put the items into the bag such that the sum of profits associated with them is the maximum possible. 

The constraint here is we can either put an item completely into the bag or cannot put it at all.

While the popular knapsack problem might deal with maximizing profit in a completely legal way, we borrow inspiration from data miners and contemplate robbing. Just that it is money instead of data and totally hypothetical of course.

We consider that every house on a street has a specific amount of money. Now, our constraint here is that adjacent houses are no-goes.

To minimize space complexity we keep tabs on the values of previous index prev and previous-to-previous index prev2 and we can calculate the value for current index cur.

class Solution 
{
public:
    int rob(vector<int>& A) {
        int prev2 = 0, prev = 0, cur = 0;
        for(auto i : A) {
            cur = max(prev, i + prev2); //here we compare the prev value and the sum of the alternate houses
            prev2 = prev; 
            prev = cur;
        }
        return cur;
    }
};

Now, if we were to add an additional constraint of the first and the last house being adjacent to each other – hence creating more of a cyclic system – we make further changes.

public:
int rob(vector<int>nums)
{
  int n=nums.size();
  if (n<2)
    return n ? nums[0]:0;
  return max(robber (nums, 0,n-2), robber (nums,1,n-1));
}
private:
int robber(vector<int>nums, int l, int r)
{
  int prev2 = 0, prev = 0, cur = 0;
  for (auto i : A)
  {
    int cur = max(prev, i + prev2)
    prev2 = prev; 
    prev = cur;
  }
  return cur;
}

Here, we divide the problem into parts and compute the maximum separately. Once by including the first house and excluding the last house, and again by excluding the first house and including the last house and finding its maximum.