198. House Robber（连续数组求不连续的最大和）

ゝ一世哀愁。 2023-07-20 13:34 2阅读 0赞

题目：在数组中，取数字来求和，求最大值多少。（要求：取的数字不能够相邻）

思路：  
1，非递归思路：至少要隔一个数字，所以将他们分为奇数和偶数位，然后分别在计算和的时候是和前一个的奇/偶的值求最大值，因为奇数偶数天然分开的，求到奇数位的最大和的时候拿它和前一个偶数位比较。  
2. 递归思路：f(n)=f(n-2)+a\[n\] 与 f(n-1) 的最大值。  
好了，递归思路出来了用循环来做。

代码：

class Solution { 
    public:
        int rob(vector<int>& nums) { 
          
            int n=nums.size();
            int tmp1,tmp2;
            tmp1=tmp2=0;
            for(int i=0;i<n;++i)
            { 
                if(i%2==0)
                   tmp1=max(tmp1+nums[i],tmp2);         //表示在前面这段当中最大值。
                else
                    tmp2=max(tmp2+nums[i],tmp1);        //奇偶是天然隔开的
            }
            return tmp1>tmp2? tmp1:tmp2;
        }
    };

代码二：

class Solution { 
    public:
        int rob(vector<int>& nums) { 
            const int n = nums.size();
            if (n == 0) return 0;
            if (n == 1) return nums[0];
            if (n == 2) return max(nums[0], nums[1]);
            vector<int> f(n, 0);
            f[0] = nums[0];
            f[1] = max(nums[0], nums[1]);
            for (int i = 2; i < n; ++i)
                f[i] = max(f[i-2] + nums[i], f[i-1]);
            return f[n-1];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，2人围观）

还没有评论，来说两句吧...

相关阅读

相关 198. House Robber（连续数组求不连续的最大和）

题目：在数组中，取数字来求和，求最大值多少。（要求：取的数字不能够相邻）思路： 1，非递归思路：至少要隔一个数字，所以将他们分为奇数和偶数位，然后分别在计算和的时候是和

ゝ一世哀愁。/ 2023年07月20日 13:34/ 0 赞/ 3 阅读

相关 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

阳光穿透心脏的1/2处/ 2022年08月21日 11:41/ 0 赞/ 154 阅读

相关 LeetCode-198. House Robber

Problem: > You are a professional robber planning to rob houses along a street. > Eac

落日映苍穹つ/ 2022年08月20日 12:28/ 0 赞/ 21 阅读

相关 leetCode198-House Robber

题目： You are a professional robber planning to rob houses along a street. Each house has

今天药忘吃喽~/ 2022年08月07日 10:55/ 0 赞/ 151 阅读

相关 leetcode 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

旧城等待，/ 2022年07月28日 01:09/ 0 赞/ 164 阅读

相关 198. House Robber （房屋盗窃）

You are a professional robber planning to rob houses along a street. Each house has a ce

港控/mmm°/ 2022年07月15日 01:21/ 0 赞/ 131 阅读

相关 LeetCode198—House Robber

原题 [原题链接][Link 1] You are a professional robber planning to rob houses along a stre

傷城~/ 2022年07月11日 12:22/ 0 赞/ 144 阅读

相关 [leetcode]: 198. House Robber

1.题目 You are a professional robber planning to rob houses along a street. Each house

ゞ浴缸里的玫瑰/ 2022年06月15日 09:14/ 0 赞/ 152 阅读

相关 LeetCode 198.House Robber (打家劫舍)

题目描述：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷

小咪咪/ 2022年04月15日 00:49/ 0 赞/ 170 阅读

相关 198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a ce

た入场券/ 2022年03月02日 08:10/ 0 赞/ 212 阅读