O(1)-space Java and C++


  • 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.

    • Java
    class Solution {
        public int rob(int[] nums) {
            int pre = 0, cur = 0;
            for (int num : nums) {
                final int temp = Integer.max(pre + num, cur);
                pre = cur;
                cur = temp;
            }
            return cur;
        }
    }
    
    • C++
    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;
        }
    };
    

  • 6
    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.


  • 0

    @wang.yi.507 Thank you for the clarification. Well, my explanation is actually based on int temp = max(pre + nums[i], cur);, which implies that pre does not rob nums[i - 1] and cur robs nums[i - 1].

    Yeah, you are right. After updating pre and cur, their meanings changed for the current loop. When the next loop begins, the above meanings still work.


Log in to reply
 

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