198. House Robber

你是一名專業的強盜，計劃搶劫沿街的房屋。每棟房子都藏有一定數量的金錢，唯一阻止你搶劫的限制是相鄰的房子都連接了安全系統，如果在同一晚闖入兩棟相鄰的房子，它會自動聯繫警察。

https://leetcode.com/problems/house-robber/

給定一個整數數組nums，表示每所房子的金額，返回你今晚可以在不觸發警報的情況下搶劫的最大金額

範例
nums = [1,2,3,1]
return 4 (搶nums[1]接nums[3]可不觸發警報下取得最多的錢)

這邊會用到子數列最大值類似的概念，相關題型可參考連結

將路線分為兩組，數列奇偶分別對不同路線進行累加，就可避免踩到連續偷竊的規則。

但還要額外考慮另一點，就是跳號也可以偷，拿範例[a,b,c,d]演示。

第一間
[a]
[ ]

第二間
[a]
[b]

第三間
[a,c]  (該欄位為[a],[c],[a+c]三者中的最大值)
[b]

第四間
[a,c]
[b,d]  (該欄位為[b],[d],[b+d]三者中的最大值)

可以發現第四間時少算了[a,d]這個組合，解決方式就是在偷新房子前，先將目前路線的金額和別路比較，比較大就替換掉；這樣就把跳號的組合也考慮進去了

還是看範例比較清楚，當第三間時

第三間
[a]        ← [c] (在c併進來前)
 ↓
[a] vs [b] (先把上路[a]的金額跟下路[b]比較，將下路金額替換為比較大的)

第四間
[a,c]
[a or b] ← [d]  (在放入第四間時，就可確保該路線是目前的最大值)

第五間之後也是同樣手法，在偷新房子前先比較兩路，取最大值再放入

寫成程式碼如下

	public int rob(int[] nums) {
		int aRoad = 0;
		int bRoad = 0;

		for (int i = 0; i < nums.length; i++) {
			if (i % 2 != 0) {
				// 奇數
				if (aRoad > bRoad) {
					// 比較兩路線金額，比另一條路還大則替換
					bRoad = aRoad;
				}
				aRoad = aRoad + nums[i];
			} else {
				// 偶數
				if (bRoad > aRoad) {
					// 比較兩路線金額，比另一條路還大則替換
					aRoad = bRoad;
				}
				bRoad = bRoad + nums[i];
			}
		}
		if (aRoad > bRoad) {
			return aRoad;
		}
		return bRoad;
	}