-
2020-10-23 12:07:14
题目:求数组中不相邻的数和的最大值。
例如:1,3,5,2,6
最大值是:5+6=11
#include <stdio.h> int a[5] = {1,3,5,2,6}; int max(int x,int y) { return x>y?x:y; } int main() { int i; int sum[5] = {0}; sum[0]=0; sum[1]=1; for(i=2; i < sizeof(a)/sizeof(int); i++){ sum[i] = max(sum[i-2]+a[i], sum[i-1]); } printf("===>%d\n",sum[i-1]); return 0; }
算法思想:采用一个求和数组,sum[i-1]表示a[i]前的元素中已经求得的最大和;
然后得出一个等式:sum[i] = max(sum[i-2]+a[i], sum[i-1]);
更多相关内容 -
LeetCode1716数组中不相邻数据和的最大值
2020-04-21 21:02:46dp[i]为0-i数组中不相邻数据的最大值,对于i个数据可以取也可以不取,若取的话则值为 dp[i-2]+nums[i],若不取的话则dp[i-1]则状态转移方程dp[i]=Max(dp[i-1],dp[i-2]+nums[i]);初始值dp[0]=nums[0],dp[1]=Max(nums...dp[i]
为0-i数组中不相邻数据的最大值,对于i
个数据可以取也可以不取,若取的话则值为dp[i-2]+nums[i]
,若不取的话则dp[i-1]
则状态转移方程dp[i]=Max(dp[i-1],dp[i-2]+nums[i])
;初始值dp[0]=nums[0]
,dp[1]=Max(nums[0],nums[1])
package BDyNamicProgramming; /** * @Author Zhou jian * @Date 2020 ${month} 2020/4/21 0021 17:16 */ public class Problem1716 { /** * dp[i]数组0-中最大和(数据不相邻) * dp[0]=nums[0],dp[1]=max(nums[0].nums[1]) * dp[i]=max(dp[i-1],dp[i-2]+nums[i]) * @param nums * @return */ public int massage(int[] nums) { if(nums.length==0) return 0; if(nums.length==1) return nums[0]; int[] dp = new int[nums.length]; dp[0]=nums[0]; dp[1]=Math.max(nums[0],nums[1]); for(int i=2;i<nums.length;i++){ dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]); } return dp[nums.length-1]; } }
-
数组中不相邻元素的最大和
2015-10-21 12:03:40数组中不相邻元素的最大和 Maximum sum such that no two elements are adjacent原题链接: Maximum sum such that no two elements are adjacent
题目
给定一个只含正数的数组,找到数组满足条件的元素的最大和,条件是:组成最大和的所有元素不能相邻,比如数组 [3,2,7,10] 返回 13(3+10),数组 [3,2,5,10,7] 返回(3+5+7)解题思路:
遍历array 中的所有元素,设置两个变量:
excl: 不包含前一个元素的最大和
incl: 包含前一个元素的最大和更新当前元素的 excl 和 incl:
不包含当前元素的最大和 excl = max(incl’, excl’)
包含当前元素的最大和 incl = excl’+current (元素不能相邻)arr[] = {5, 5, 10, 40, 50, 35} 1) arr[0] = 5 incl = 5 excl = 0 2) arr[1] = 5 incl = (excl + arr[1]) = 5 excl = max(5, 0) = 5 3) arr[2] = 10 incl = (excl + arr[2]) = 15 excl = max(5, 5) = 5 4) arr[3] = 40 incl = (excl + arr[3]) = 45 excl = max(5, 15) = 15 5) arr[4] = 50 incl = (excl + arr[4]) = 65 excl = max(15, 45) = 45 5) arr[5] = 35 incl = (excl + arr[5]) = 80 excl = max(45, 65) = 65 answer is max(incl, excl) = 80
代码
#include <iostream> using namespace std; int maxSum(int *arr, int size) { if(size<=0) return 0; else if(size ==1) return arr[0]; int excl = 0, incl = arr[0]; int excl_new; for(int i = 1; i<size; ++i) { excl_new = (excl>incl)?excl:incl; incl = excl + arr[i]; excl = excl_new; } return (incl>excl)?incl:excl; } int main() { int array[] = {5,5,10,40,50,35}; cout<<maxSum(array, 6)<<endl; }
-
LeetCode精讲(0198):计算数组中不相邻组合的最大和(Python)
2020-06-18 11:38:42LeetCode精讲(0198):计算数组中不相邻组合的最大和(Python) 题目内容 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两...题目内容
你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。
示例 1:
输入:[1,2,3,1] 输出:4 解释:偷窃 1 号房屋 (金额 = 1) ,然后偷窃 3 号房屋 (金额 = 3)。 偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入:[2,7,9,3,1] 输出:12 解释:偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9),接着偷窃 5 号房屋 (金额 = 1)。 偷窃到的最高金额 = 2 + 9 + 1 = 12 。
提示:
0 <= nums.length <= 100
0 <= nums[i] <= 400
标签:动态规划
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/house-robber
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解法效率
解法 执行用时 Ans 1 (Python) 超出时间限制 Ans 2 (Python) 32ms (>96.24%) Ans 3 (Python) 40ms (>68.74%) 解法一(动态规划):
【思路】 简单思考,得到如下思路:
如果想取得最大值,那数组中每两个相邻的取值之间,只可能间隔1个数或2个数,开头有两种选择,从第一个数开始取和从第二个数开始取。
所以如果在取得第i个数,此时其最大值只能来自:取得第i-2个数的最大值再加第i个数、取得第i-3个数的最大值再加第i个数。
又有当i=0时,最大值为nums[0];当i=1时,最大值为nums[1];当i=2时,最大值为nums[0]+nums[2];当i>=3时,可使用上一段的方法计算。
最终数列取得的最大值为取得nums[-1]和取得nums[-2]的两个最大值中更大的那一个。
由此得出如下初步的逻辑(这要真能运行也会慢死):
def rob(self, nums: List[int]) -> int: def helper(i): if i == 0: return nums[0] elif i == 1: return nums[1] elif i == 2: return nums[0] + nums[2] else: return max(helper(i - 2), helper(i - 3)) + nums[i] size = len(nums) if size == 0: return 0 elif size == 1: return nums[0] else: return max(helper(size - 1), helper(size - 2))
解法二(滚动数组):
【思路】对以上算法进行优化,改用滚动数组的方法,将其空间复杂度优化为O(1),时间复杂度优化为O(n)。
def rob(self, nums: List[int]) -> int: size = len(nums) if size == 0: return 0 elif size == 1: return nums[0] elif size == 2: return max(nums[0], nums[1]) else: sum_1 = nums[0] # 取得第i-3个数的最大值 sum_2 = nums[1] # 取得第i-2个数的最大值 sum_3 = nums[0] + nums[2] # 取得第i-1个数的最大值 for i in range(3, size): n = nums[i] sum_4 = max(sum_1 + n, sum_2 + n) # 取得第i个数的最大值 sum_1 = sum_2 sum_2 = sum_3 sum_3 = sum_4 return max(sum_2, sum_3)
解法三(更简单的思路):
【思路】此时,我们还有一个更简单的思路:
我们可以不再考虑取得某个数时的最大值,改为考虑截止到某个数的最大值。
此时,如果我们取得的某两个数(第i个数和第i+3个数)之间间隔了2个数,那么说明截止到第i个数的最大值和截止到第i+1个数的最大值是相同的。
因此,当我们改为考虑截止到某个数的最大值时,截止到第i个数的最大值只可能来自:截止到第i-2个数的最大值加第i个数、截止到第i-1个数的最大值。
由此如下的逻辑:
def rob(self, nums: List[int]) -> int: size = len(nums) if size == 0: return 0 elif size == 1: return nums[0] else: sum_1 = nums[0] sum_2 = max(nums[0], nums[1]) for i in range(2, size): sum_3 = max(sum_1 + nums[i], sum_2) sum_1 = sum_2 sum_2 = sum_3 return max(sum_1, sum_2)
-
记录---求数组中不相邻元素的最大和(动态规划)
2020-08-31 22:43:25输入一个只含正数的数组,找到数组满足条件的元素的最大和,条件... * 数组中不相邻数字相加最大和 * */ public class DP1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Stri -
数组不相邻元素最大和的解法(动态规划)
2021-07-23 10:38:33给定数组,要求不相邻元素组成的子数组的和最大. public class Test { public static void main(String[] args) { int[] arr = {1, 3, 5, 2, 7, 9, 4, 8, 6}; System.out.println(maxNoNeighborhoodSum(arr... -
java获取数组中最大差值
2021-03-16 15:43:27获取数组中最大差值 -
【动态规划】求数组不相邻元素之和最大
2018-10-31 23:00:07微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的读书笔记!期待您的关注,欢迎一起学习交流进步! 知乎专栏:... -
动态规划-求一个数组中不相邻的数值的和的最大值
2021-05-13 18:30:45如一个数组是这样的:[1,4,3,5],那么最后和为下标第1个4和下标第三个5组成最大值9. 通常在这种情况下,我会以最后一个数值从后往前进行一个推理。以[1,4,3,5]为例,当我们选择5这个数的时候,那么它就不能选择3而... -
动态规划 求数组中不相邻元素的最大和
2021-05-06 20:48:40找出相加最大的和,选择的数不能相邻 该数组解为 1,4,7,3 和为15 题解: b站视频讲解 https://www.bilibili.com/video/BV12W411v7rd?from=search&seid=16185215057279292603 从最后一个来是按照递归的思想... -
数组不相邻元素之和的最大值
2018-08-19 17:22:00数组不相邻元素之和的最大值 一、题目描述 今天下午面试老虎证券,被问到这题,当时脑子有点蒙,代码没写出来。这题的意思就是给你一个数组,让你计算元素的和,但是这些元素都不能相邻,求最大的... -
C++实现从数组中同时取出最大最小元素算法示例
2021-01-20 06:35:25本文实例讲述了C++实现从数组中同时取出最大最小元素的方法。分享给大家供大家参考,具体如下: 算法思想:先相邻两个两个比较,较大的放入数组max[],较小的放入数组min[],然后从max[]数组求出最大,min[]数组求出... -
数组排序之后相邻数的最大差值
2022-03-31 21:15:39给定一个整形数组arr,返回排序后相邻两数的最大差值 arr = [9, 3, 1, 10]。如果排序,结果为[1, 3, 9, 10],9和3的差为最大差值,故返回6。 arr = [5, 5, 5, 5]。返回0。 [要求] 时间复杂度为O(n),空间复杂度为O(n... -
LeetCode(198)-House Robber/找出数组中不相邻元素最大和(动态规划)
2019-05-27 16:50:11此题就是让我们在一个数组中找到一些数,使得这些数之和最大,其中这些数两两不能相邻。 对于每个元素来说,要么被选上,要么没有被选上。实际上,这道题变成了求最后一个选上没有选上的最大值问题。因此我们使用两... -
数组相邻元素之和的最大值
2022-01-13 10:51:13编写一个程序,求一个有N个元素的整型数组中子数组之和的最大值,子数组指的是一个数组中连续的若干个相邻的元素。 思路一:暴力破解,逐个相加比较,求最大值(效率地) 代码: #include<stdio.h> #define... -
[算法题] 求数组有序后相邻元素之间的最大差值
2021-04-22 18:29:441. 题目要求给定无序数组(此数组是long类型的数组,但以下示例只列一些小一点的数),例如:[3, 1, 12, 9, 3, 7, 1, 4, 7, 8, 10]求数组有序后相邻元素之间的最大差值,数组有序后如下:[1, 1, 3, 3, 4, 7, 7, 8, 9, ... -
随笔-最大间距/数组中相邻元素的最大差值
2018-12-28 13:16:09解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) 和 (6,9) 之间都存在最大差值 3。 示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。 说明: 你可以假设数组中所有元素都... -
算法题_给定一个数组求数组中相邻元素差的最大公约数
2020-04-08 18:12:23题目: 给定一个数组,数组中相邻的元素之间的差都是d的k倍(1 <= k),求这个d是否存在。若存在,输出d的值;如不存在,则输出-1。 思路: 我们可以采用辗转相除法和辗转相减法求出最大公约数。 接下来我们用C++... -
House Robber I - 由数组中不相邻元素组成的子数组,使其和最大
2017-02-15 08:47:10假设a[0~2]的最大不相邻子数组a2用到了最后一个元素,那么a[0~3]的最大不相邻的子数组肯定不是a2+a[3]; 假设a[0~2]的最大不相邻子数组a2没有用到最后一个元素,那么a[0~2]等于a[0~1]的最大不相邻子数组; ... -
不相邻元素正数数组最大和值
2018-08-24 09:56:081)子数组选择的元素不能包含原数组相邻元素 2)满足条件1的前提下,得到的子数组的和值最大 思路:遍历一次数组,设置两个变量: 包含当前元素的最大值 curMax 包含前一个元素的最大值preMax 在遍历过程过... -
取数组中任意个数相加,但是取的数不能相邻,输出最后得到的和的最大值
2021-03-27 11:57:01提供一个数组,取数组中任意个数相加,但是取的数不能相邻,输出最后得到的和的最大值,输入的数组的值均为正整数。 样例 输入:[ 2, 3, 2 ] 输出:4 说明:取第1个值和第三个值,2+2 = 4 分析 动态规划。... -
算法题巧解之数组排序后相邻最大差值
2018-05-29 20:59:47题目:给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(N) 例: 数组 arr =[1,3,2,5,8,6] 输出结果:2 看到这个题目我的第一反应是通过多次遍历的这样暴力手段来解决(请原谅我的菜和... -
求一个数组中非相邻元素和的最大值问题(动态规划)
2020-07-17 16:04:03求一个数组中非相邻元素和的最大值问题 视频地址 1.递归版本 public class Test { public static int rec_opt(int[] arr, int len) { if(len==0) return arr[0]; else if(len==1) return Math.max(arr[0... -
无序数组的相邻最大差值
2017-09-18 13:30:15题目描述:请设计一个复杂度为O(n)的算法,计算一个未排序数组中排序后相邻元素的最大差值。 给定一个整数数组A和数组的大小n,请返回最大差值。保证数组元素个数大于等于2小于等于500。 测试样例: [9,3,1,10],4...