House Robber

Medium Dynamic Programming

Given money in each house, find the maximum you can rob without taking from two adjacent houses. O(1) space rolling DP.

Sample input

[2, 7, 9, 3, 1]

Sample output

Solution

def rob(nums):
    prev = curr = 0
    for num in nums:
        prev, curr = curr, max(curr, prev + num)
    return curr

print(rob([2, 7, 9, 3, 1]))

function rob(nums) {
  let prev = 0, curr = 0;
  for (const num of nums) {
    const temp = Math.max(curr, prev + num);
    prev = curr;
    curr = temp;
  }
  return curr;
}

console.log(rob([2, 7, 9, 3, 1]));

public class Main {
    static int rob(int[] nums) {
        int prev = 0, curr = 0;
        for (int num : nums) {
            int temp = Math.max(curr, prev + num);
            prev = curr;
            curr = temp;
        }
        return curr;
    }

    public static void main(String[] args) {
        System.out.println(rob(new int[]{2, 7, 9, 3, 1}));
    }
}

fun rob(nums: IntArray): Int {
    var prev = 0
    var curr = 0
    for (num in nums) {
        val temp = maxOf(curr, prev + num)
        prev = curr
        curr = temp
    }
    return curr
}

fun main() {
    println(rob(intArrayOf(2, 7, 9, 3, 1)))
}

func rob(_ nums: [Int]) -> Int {
    var prev = 0, curr = 0
    for num in nums {
        let temp = max(curr, prev + num)
        prev = curr
        curr = temp
    }
    return curr
}

print(rob([2, 7, 9, 3, 1]))

int rob(List<int> nums) {
  int prev = 0, curr = 0;
  for (final num in nums) {
    final temp = curr > prev + num ? curr : prev + num;
    prev = curr;
    curr = temp;
  }
  return curr;
}

void main() {
  print(rob([2, 7, 9, 3, 1]));
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int rob(const vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int num : nums) {
        int temp = max(curr, prev + num);
        prev = curr;
        curr = temp;
    }
    return curr;
}

int main() {
    cout << rob({2, 7, 9, 3, 1}) << endl;
    return 0;
}

#include <stdio.h>

int rob(int *nums, int n) {
    int prev = 0, curr = 0;
    for (int i = 0; i < n; i++) {
        int temp = curr > prev + nums[i] ? curr : prev + nums[i];
        prev = curr;
        curr = temp;
    }
    return curr;
}

int main() {
    int nums[] = {2, 7, 9, 3, 1};
    printf("%d\n", rob(nums, 5));
    return 0;
}