198. House Robber

Problem Statement

Pattern:

---

Recursive Solution

private class Pair {
	int inSum;
	int exSum;
	Pair (int inSum, int exSum) {
		this.inSum = inSum;
		this.exSum = exSum;
	}
}
 
Pair maxSum (LinkedList<Integer> list) {
	if(list.isEmpty()) return new Pair(0, 0);
 
	int num = list.remove();    // remove first
 
	Pair next = maxSum(list);
	int inSum = num + next.exSum;
	int exSum = Math.max(next.exSum, next.inSum);
 
	return new Pair(inSum, exSum);
}
 
public int rob (int[] nums){
	LinkedList<Integer> list = new LinkedList<>();
	for (int num : nums) list.add(num);
 
	Pair max = maxSum(list);
 
	return(Math.max(max.inSum, max.exSum));
}

Much like : Maxiumum Sum of Non-Adjacent Nodes

Iterative Solution

No callstack! and No unnecessary object creation! much faster !!!

private class Pair {
	int inSum;
	int exSum;
 
	Pair(int inSum, int exSum) {
		this.inSum = inSum;
		this.exSum = exSum;
	}
}
 
int rob(int[] nums) {
	Pair prev = new Pair(0, 0);
	for (int num : nums) {
		int inSum = prev.inSum;
		prev.inSum = prev.exSum + num;
		prev.exSum = Math.max(prev.exSum, inSum);
	}
	return Math.max(prev.exSum, prev.inSum);
}

Same solution except we can move iterativel

Simplified Iterative

public int rob(int[] num) {
    int prevNo = 0;
    int prevYes = 0;
    for (int n : num) {
        int temp = prevNo;
        prevNo = Math.max(prevNo, prevYes);
        prevYes = n + temp;
    }
    return Math.max(prevNo, prevYes);
}