首页 > 代码库 > LintCode 392 House Robber
LintCode 392 House Robber
// Ref: https://segmentfault.com/a/1190000003811581
// Ref: http://www.cnblogs.com/grandyang/p/4383632.html
/*
如果选择了抢劫上一个屋子,那么就不能抢劫当前的屋子,所以最大收益就是抢劫上一个屋子的收益
如果选择抢劫当前屋子,就不能抢劫上一个屋子,所以最大收益是到上一个屋子的上一个屋子为止的最大收益,加上当前屋子里有的钱
*/
1 public static long houseRobber(int[] A) { 2 int len = A.length; 3 if (len <= 1) { 4 return len == 0 ? 0: A[0]; 5 } 6 7 long previous = A[0]; // a is the previous max 8 long current = Math.max(A[0], A[1]); // b is the current max 9 for(int i = 2; i < len; i++){ 10 long tmp = current; 11 // previous + A[i] => pre-pre + current 12 // b/c it cannot rob adjacent houses => need to compare 13 current = Math.max(previous + A[i], current); 14 previous = tmp; 15 } 16 return current; 17 }
LintCode 392 House Robber
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。