【每日算法Day 105】打家劫舍第二弹：看好你的电瓶车！

题目链接

LeetCode 213. 打家劫舍 II^[1]

往期回顾：打家劫舍 I ：

【每日算法Day 104】偷电瓶的周某今天放出来了，还不赶紧做这道题防范一下！^[2]

题目描述

你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都围成一圈，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。

示例1

输入：[2,3,2]输出:3

示例2

输入：[1,2,3,1]输出:4

题解

代码

c++

classSolution {
public:   
introb1(vector<int>&nums, intl, intr) {
intprepre=0, pre=0, now=0; 
for (inti=l; i<=r; ++i) {    
now=max(pre, prepre+nums[i]);  
prepre=pre;     
pre=now;      
        }      
returnnow;   
    }
introb(vector<int>&nums) {  
intn=nums.size();    
if (n==1) returnnums[0];  
inta=rob1(nums, 0, n-2);   
intb=rob1(nums, 1, n-1);   
returnmax(a, b);  
    }
};

参考资料

[1]

LeetCode 213. 打家劫舍 II: https://leetcode-cn.com/problems/house-robber-ii/

[2]

【每日算法Day 104】偷电瓶的周某今天放出来了，还不赶紧做这道题防范一下！: https://godweiyang.com/2020/04/18/leetcode-198/

作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~