1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
| #include<iostream>
#include<set>
#include<vector>
using namespace std;
class Solution {
public:
int MAX(vector<int>&arr,int n,vector<int>&data)
{
int max,i,k=0;
max = arr[0];
for (i=1; i <= n; i++) {
if (arr[i] >= max) {
max = arr[i];
k=i;
}
}
if(data[k]==1||k==0)
data[n+2]=1;
return max;
}
int MAXL(vector<int>&arrl,int n)
{
int max=arrl[0];
for(int i=1;i<n;i++)
{
if(arrl[i]>max)
max=arrl[i];
}
return max;
}
void last(vector<int>&arr,vector<int>&data,vector<int>&nums)
{
int max1=arr[1];
int max2=arr[1];
for(int i=1;i<nums.size()-2;i++)
{
//最大的价值包含1号房子
if(arr[i]>max1&&data[i]==1) {
max1 = arr[i];
}
//最大的价值不包含1号房子
if(arr[i]>max2&&data[i]==0)
{
max2=arr[i];
}
}
//判断包含1号房子的最大价值加上最后一所房子的价值然后再减去1号房子的价值(相当于没有首尾连续偷) > 不包含1号房子的价值加上最后一所房子的价值 ？
//取最大值作为最后一所房子所能获得的最大的价值
arr[arr.size()-1]=max(max1+nums[nums.size()-1]-nums[0],max2+nums[nums.size()-1]);
}
int rob(vector<int>& nums) {
//如果nums的长度小于等于3,直接判断最大值
if(nums.size()==NULL)
return 0;
if(nums.size()==1)
return nums[0];
if(nums.size()==2)
return max(nums[0],nums[1]);
if(nums.size()==3)
return max(max(nums[0],nums[1]),nums[2]);
//当nums的长度大于3
vector<int>arr(nums.size(),0); //存放偷数组下标从0位置的房子到n-2位置房子的值
vector<int>data(nums.size(),0); //给定一个标记，如果偷的房子的价值包含nums[0]的就标记为1，没有的就标记为0
vector<int>arrl(nums.size()-1,0);//存放偷数组下标从1位置的房子到n-1位置房子的值
data[0]=1; //第一个房子标记为1(房子标号从1号开始)
data[2]=1; //第三个房子也标记为1，因为现在房子数大于3，可以偷了1号房子和3号房子获得最大值
arr[0]=nums[0]; //存放偷1号房子可以获得的最大价值
arr[1]=nums[1]; //存放偷2号房子可以获得的最大价值
for(int i=2;i<nums.size()-1;i++)
//我们需要在arr数组中找出下标i-2前最大的那个然后再加上nums[i]存入arr[i];
arr[i] = nums[i] + MAX(arr, i - 2, data);
//我们需要从2号房子算起，看偷最后一所房子的最大价值
last(arr,data,nums);
arrl[0]=nums[1];
arrl[1]=nums[2];
//现在我们只要计算最后一所房子的价值，和上边一样，重新更新一次arr的值，不过我们将新得到的数存在arrl里面
for(int i=3;i<nums.size();i++)
arrl[i-1]=nums[i]+MAXL(arrl,i-2);
//判断如果arrl里面的最后一所房子的价值大于arr里面最后一所房子的价值，直接更新arr最后一所房子的价值，此时才是最后一所房子的最大价值
if(arr[arr.size()-1]<arrl[arrl.size()-1])
arr[arr.size()-1]=arrl[arrl.size()-1];
//找出最大的那个值
int max=arr[0];
for(int i=1;i<arr.size();i++)
{
if(arr[i]>max)
max=arr[i];
}
return max;
}
};
int main()
{
vector<int>a={1,2,3,1};
cout<<Solution().rob(a)<<endl;
return 0;
}
|
