Create house-robber.py

kamyu104 · kamyu104 · commit 6fcc8dcb117d · 2015-04-01T23:01:07.000+08:00
diff --git a/Python/house-robber.py b/Python/house-robber.py
@@ -0,0 +1,30 @@
+# Time:  O(n)
+# Space: O(1)
+#
+# You are a professional robber planning to rob houses along a street. 
+# Each house has a certain amount of money stashed, the only constraint stopping you 
+# from robbing each of them is that adjacent houses have security system connected
+# and it will automatically contact the police if two adjacent houses were broken into on the same night.
+#
+# Given a list of non-negative integers representing the amount of money of each house, 
+# determine the maximum amount of money you can rob tonight without alerting the police.
+#
+class Solution:
+    # @param num, a list of integer
+    # @return an integer
+    def rob(self, num):
+        if len(num) == 0:
+            return 0
+            
+        if len(num) == 1:
+            return num[0]
+        
+        num_i, num_i_1 = max(num[1], num[0]), num[0]
+        for i in xrange(2, len(num)):
+            num_i_1, num_i_2 = num_i, num_i_1
+            num_i = max(num[i] + num_i_2, num_i_1);
+        
+        return num_i
+
+if __name__ == '__main__':
+        print Solution().rob([8,4,8,5,9,6,5,4,4,10])
