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


  • 4
    T

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

    class Solution {
    public:
    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.