O(N) time O(1) space C++ solution

  • 4

    a classical DP solution: p: the solution to subarray [0..i-1], q: the solution to subarray [0..i-2]

    class Solution {
    int rob(vector<int>& nums) {
        int p = 0, q = 0;
        for (auto n: nums) {
            int tmp = p;
            p = max(p, q + n);
            q = tmp; 
        return p;

Log in to reply

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