Another DP solution. 10 lines and 0ms


  • 0
    F
    int rob(vector<int>& nums) {
        int n = nums.size();
        if(n == 0 ) return 0;
        vector<int> maxRob0(n+1, 0);  //not taking the last
        vector<int> maxRob1(n+1, 0); //taking the last
        maxRob1[n-1] = nums[n-1];
        for(int i=n-2; i>=0; --i) {
            maxRob0[i] = max(nums[i] + maxRob0[i+2], maxRob0[i+1]);
            maxRob1[i] = max(nums[i] + maxRob1[i+2], maxRob1[i+1]);
        }
        return max(maxRob0[0], n == 1 ? maxRob1[0] : maxRob1[1]);
    }

Log in to reply
 

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