House Robber II Solutions in C++

// Source : https://leetcode.com/problems/house-robber-ii/
// Author : Hao Chen
// Date   : 2015-06-10




class Solution {
public:
    int orginal_rob(vector<int> &money, int start, int end) {
        int n2=0; 
        int n1=0; 
        
        for (int i=start; i<end; i++){
            int current = max(n1, n2 + money[i]);
            n2 = n1;
            n1 = current;
        }
        return n1;
    }
    
    int rob(vector<int>& nums) {
        int n = nums.size();
        switch (n) {
            case 0:
                return 0;
            case 1:
                return nums[0];
            case 2:
                return max(nums[0], nums[1]);
            default:
                /*
                 * the idea is we cannot rob[0] and rob[n-1] at same time
                 * so, we rob [0 .. n-2] or [1 .. n-1], can return the maxinum one.
                 */
                int m1 = orginal_rob(nums, 0, n-1);
                int m2 = orginal_rob(nums, 1, n);
                
                return max(m1, m2);
        }
    }
};

/// Source : https://leetcode.com/problems/house-robber-ii/description/
/// Author : liuyubobobo
/// Time   : 2017-11-15

#include <iostream>
#include <vector>

using namespace std;

/// Dynamic Programming
/// Two Pass House Robber I Problem
/// Time Complexity: O(n)
/// Space Complexity: O(1)
class Solution {
public:
    int rob(vector<int>& nums) {

        int n = nums.size();

        if(n == 0)
            return 0;

        if(n == 1)
            return nums[0];

        if(n == 2)
            return max(nums[0], nums[1]);

        return max(rob(nums, 0, nums.size() - 2), rob(nums, 1, nums.size() - 1));
    }

private:
    int rob(const vector<int>& nums, int start, int end){

        int preMax = nums[start];
        int curMax = max(preMax, nums[start+1]);
        for(int i = start + 2 ; i <= end ; i ++){
            int temp = curMax;
            curMax = max(nums[i] + preMax, curMax);
            preMax = temp;
        }

        return curMax;
    }
};

int main() {

    vector<int> nums = {2, 7, 9, 3, 1};
    cout << Solution().rob(nums) << endl;

    return 0;
}