C++刷面试题（数组中不能连着取求最大和）

糖逗

题目描述：

1. 给定一个数组，数组中的数不能连着取，求最大的和。
   
2. 如[7,5,4,2,1]最大的为7+4+1

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. using namespace std;
   
4. 
   
5. 
   
6. 
   
7. int dfs(vector<int> & input, int i, vector<int> & visit){
   
8.         if(i >= input.size()) return 0;
   
9.         if(visit[i] > 0) return visit[i];
   
10.        
    
11.         int temp = 0;
    
12.         for(int j = i+2; j < input.size(); j++){
    
13.                 temp = max(temp, dfs(input, j, visit));
    
14.         }
    
15.         visit[i] = temp + input[i];
    
16.         return temp + input[i];
    
17. }
    
18. 
    
19. 
    
20. 
    
21. int solution(int* input, int len){
    
22.         int res = 0;
    
23.         vector<int> temp;
    
24.         for(int i = 0 ; i < len; i++){
    
25.                 temp.push_back(*(input + i));
    
26.         }
    
27.        
    
28.         vector<int> visit (len, 0);
    
29.         for(int i = 0; i < len; i++){
    
30.                 if(visit[i] == 0){
    
31.                         res = max(res, dfs(temp, i, visit));
    
32.                 }
    
33.                 else{
    
34.                         res = max(res, visit[i]);
    
35.                 }
    
36.                
    
37.         }
    
38.         return res;
    
39. }
    
40. 
    
41. 
    
42. 
    
43. int main(void){
    
44.         cout << "send the len" << endl;
    
45.         int len;
    
46.         cin >> len;
    
47.         cin.clear();
    
48.         int number;
    
49.         int input[len];
    
50.         int i = 0;
    
51.         while(cin >> number){
    
52.                 input[i] = number;
    
53.                 i++;
    
54.         }
    
55.         cout << solution(input, len);
    
56.         return 0;
    
57. }

复制代码

注意事项:
1.运用了动态规划和深度优先搜索，想法源自leetcode329. 矩阵中的最长递增路径。
2.使用数组不习惯，自行换成了vector。

糖逗

原题变性：198. 打家劫舍

1. 你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
   
2. 
   
3. 给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
   
4. 
   
5. 示例 1:
   
6. 
   
7. 输入: [1,2,3,1]
   
8. 输出: 4
   
9. 解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
   
10. &#160;    偷窃到的最高金额 = 1 + 3 = 4 。
    
11. 示例 2:
    
12. 
    
13. 输入: [2,7,9,3,1]
    
14. 输出: 12
    
15. 解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
    
16. &#160;    偷窃到的最高金额 = 2 + 9 + 1 = 12 。
    
17. 
    
18. 来源：力扣（LeetCode）
    
19. 链接：https://leetcode-cn.com/problems/house-robber
    
20. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <vector>
   
3. 
   
4. 
   
5. using namespace std;
   
6. 
   
7. 
   
8. int solution(vector<int>& input){
   
9.         int len = input.size();
   
10.         if(len == 0) return 0;
    
11.         vector<int> temp (len+1, 0);
    
12.         temp[0] = 0;
    
13.         temp[1] = input[0];
    
14.         for(int i = 2; i < len+1; i++){
    
15.                 temp[i] = max(temp[i-1] , temp[i-2] + input[i-1]);
    
16.         }
    
17.         return temp[len];
    
18. }
    
19. 
    
20. 
    
21. 
    
22. 
    
23. 
    
24. int main(void){
    
25.         vector<int> input;
    
26.         int number;
    
27.         while(cin >> number){
    
28.                 input.push_back(number);
    
29.         }
    
30.         cout << solution(input) << endl;
    
31.         return 0;
    
32. }

复制代码

参考链接：https://leetcode-cn.com/problems ... she-by-guanpengchn/

糖逗

一开始想复杂了，实际上原题是leetcode中打家劫舍第一题的变型，用动态规划做就可以了。