6-lines 5ms O(1)-Space C++ Solution


  • 16

    Since we are not allowed to rob two adjacent houses, we keep two variables pre and cur. During the i-th loop, pre records the maximum profit that we do not rob the i - 1-th house and thus the current house (the i-th house) can be robbed while cur records the profit that we have robbed the i - 1-th house.

    The code is as follows.

    class Solution {
    public: 
        int rob(vector<int>& nums) {
            int n = nums.size(), pre = 0, cur = 0;
            for (int i = 0; i < n; i++) {
                int temp = max(pre + nums[i], cur);
                pre = cur;
                cur = temp;
            }
            return cur;
        }
    };

  • 5
    W

    well, the solution is correct, but the explanation is wrong,
    pre is the max value at i-2
    and cur is the max value at i-1, that's why you update pre and cur after you get temp, which is the max value at i.


Log in to reply
 

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