My C++ solution, O(n) space


  • 0
    public:
        int rob(vector<int>& nums) {
            if (!nums.size()) return 0;
            if (nums.size() <= 3) return *max_element(nums.begin(), nums.end());
            vector<vector<int>> a(2, vector<int>(nums.size(),0));
            a[0][0] = nums[0]; a[1][0] = 0;
            a[0][1] = a[1][1] = nums[1];
            a[0][2] = nums[2] + nums[0]; a[1][2] = nums[2];
            for (int i = 3; i < nums.size(); i++) {
                a[0][i] = max(a[0][i-2], a[0][i-3]) + nums[i];
                a[1][i] = max(a[1][i-2], a[1][i-3]) + nums[i];
            }
            int b = *(max_element(a[0].begin(), a[0].end() - 1));
            return max(b, a[1].back());
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.