198_house_robber.cpp

/*
LeetCode 198 - House Robber
Difficulty: Medium

Problem:
You are a professional robber planning to rob houses along a street. Each house has a certain
amount of money stashed. The only constraint stopping you from robbing all of them is that
adjacent houses have security systems connected, which will automatically contact the police
if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the
maximum amount of money you can rob tonight without alerting the police.

Example 1:
    Input: nums = [1,2,3,1]
    Output: 4
    Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).

Example 2:
    Input: nums = [2,7,9,3,1]
    Output: 12
    Explanation: Rob house 1 (2) + house 3 (9) + house 5 (1) = 12.

Constraints:
    1 <= nums.length <= 100
    0 <= nums[i] <= 400

Time Complexity: O(n)
Space Complexity: O(1)
*/

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int rob(vector<int>& nums) {
        int prev2 = 0, prev1 = 0;
        for (int num : nums) {
            int temp = prev1;
            prev1 = max(prev1, prev2 + num);
            prev2 = temp;
        }
        return prev1;
    }
};

int main() {
    Solution solution;

    vector<int> nums1 = {1, 2, 3, 1};
    cout << solution.rob(nums1) << endl;  // 4

    vector<int> nums2 = {2, 7, 9, 3, 1};
    cout << solution.rob(nums2) << endl;  // 12

    return 0;
}