LeetCode 198

House Robber

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.

 1 /*************************************************************************
 2     > File Name: LeetCode198.c
 3     > Author: Juntaran
 4     > Mail: JuntaranMail@gmail.com
 5     > Created Time: Wed 11 May 2016 15:24:30 PM CST
 6  ************************************************************************/
 7  
 8 /*************************************************************************
 9     
10     House Robber
11     
12     You are a professional robber planning to rob houses along a street. 
13     Each house has a certain amount of money stashed, 
14     the only constraint stopping you from robbing each of them 
15     is that adjacent houses have security system connected 
16     and it will automatically contact the police 
17     if two adjacent houses were broken into on the same night.
18 
19     Given a list of non-negative integers representing 
20     the amount of money of each house, 
21     determine the maximum amount of money 
22     you can rob tonight without alerting the police.
23 
24  ************************************************************************/
25 
26 #include <stdio.h>
27 
28 /* 改变了原数组的值 */
29 int rob( int* nums, int numsSize )
30 {
31     if( numsSize == 0 )
32     {
33         return 0;
34     }
35     if( numsSize == 1 )
36     {
37         return nums[0];
38     }
39     
40     nums[1] = nums[0]>nums[1] ? nums[0] : nums[1];
41     
42     int i;
43     for( i=2; i<=numsSize-1; i++ )
44     {
45         nums[i] = (nums[i-2]+nums[i])>nums[i-1] ? (nums[i-2]+nums[i]) : nums[i-1];
46     }
47     return nums[numsSize-1];
48 }
49 
50 /* 两个变量共同维护 */
51 int rob2( int* nums, int numsSize )
52 {
53     if( numsSize == 0 )
54     {
55         return 0;
56     }
57     if( numsSize == 1 )
58     {
59         return nums[0];
60     }
61     
62     int prev1 = 0;
63     int prev2 = 0;
64     
65     int i, temp;
66     for( i=0; i<=numsSize-1; i++ )
67     {
68         temp = prev1;
69         prev1 = (prev2+nums[i])>prev1 ? (prev2+nums[i]) : prev1;
70         prev2 = temp;
71     }
72     return prev1;
73 }
74 
75 
76 
77 
78 int main()
79 {
80     int nums[] = { 2,1,1,4,0 };
81     int numsSize = 5;
82     
83     int ret = rob2( nums, numsSize );
84     printf("%d
", ret);
85     return 0;
86 }