LeetCode213(2021.4.15)

LC213. 打家劫舍 II

class Solution {
public:
    int rob(vector<int> &nums) {
        int n = nums.size();
        if (n == 1) return nums[0];
        if (n == 2) return max(nums[0], nums[1]);
        //取第一间
        int fst = nums[0], sec1 = max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; ++i) {
            int tmp = sec1;
            sec1 = max(fst + nums[i], sec1), fst = tmp;
        }
        //取最后一间
        int sec2 = max(nums[1], nums[2]);
        fst = nums[1];
        for (int i = 3; i < n; ++i) {
            int tmp = sec2;
            sec2 = max(fst + nums[i], sec2), fst = tmp;
        }
        return max(sec1, sec2);
    }
};

发表评论