精华内容
下载资源
问答
  • 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]);

     

     

     

     

    更多相关内容
  • 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...

    联结

    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) 题目内容 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两...

    题目内容

    你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两间相邻的房屋在同一晚上被小偷闯入,系统会自动报警。

    给定一个代表每个房屋存放金额的非负整数数组,计算你 不触动警报装置的情况下 ,一夜之内能够偷窃到的最高金额。

    示例 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)
    
    展开全文
  • 输入一个只含正数的数组,找到数组满足条件的元素的最大和,条件... * 数组中不相邻数字相加最大和 * */ public class DP1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Stri
  • 给定数组,要求不相邻元素组成的子数组和最大. 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...
  • 获取数组中最大差值
  • 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程的读书笔记!期待您的关注,欢迎一起学习交流进步! 知乎专栏:...
  • 如一个数组是这样的:[1,4,3,5],那么最后为下标第1个4下标第三个5组成最大值9. 通常在这种情况下,我会以最后一个数值从后往前进行一个推理。以[1,4,3,5]为例,当我们选择5这个数的时候,那么它就能选择3而...
  • 找出相加最大,选择的数相邻数组解为 1,4,7,3 为15 题解: b站视频讲解 https://www.bilibili.com/video/BV12W411v7rd?from=search&seid=16185215057279292603 从最后一个来是按照递归的思想...
  • 数组不相邻元素之最大

    千次阅读 2018-08-19 17:22:00
    数组不相邻元素之最大值 一、题目描述 今天下午面试老虎证券,被问到这题,当时脑子有点蒙,代码没写出来。这题的意思就是给你一个数组,让你计算元素的,但是这些元素都相邻,求最大的...
  • 本文实例讲述了C++实现从数组中同时取出最大最小元素的方法。分享给大家供大家参考,具体如下: 算法思想:先相邻两个两个比较,较大的放入数组max[],较小的放入数组min[],然后从max[]数组求出最大,min[]数组求出...
  • 给定一个整形数组arr,返回排序后相邻两数的最大差值 arr = [9, 3, 1, 10]。如果排序,结果为[1, 3, 9, 10],93的差为最大差值,故返回6。 arr = [5, 5, 5, 5]。返回0。 [要求] 时间复杂度为O(n),空间复杂度为O(n...
  • 此题就是让我们在一个数组中找到一些数,使得这些数之和最大,其中这些数两两相邻。 对于每个元素来说,要么被选上,要么没有被选上。实际上,这道题变成了求最后一个选上没有选上的最大值问题。因此我们使用两...
  • 编写一个程序,求一个有N个元素的整型数组中子数组最大值,子数组指的是一个数组中连续的若干个相邻的元素。 思路一:暴力破解,逐个相加比较,求最大值(效率地) 代码: #include<stdio.h> #define...
  • 1. 题目要求给定无序数组(此数组是long类型的数组,但以下示例只列一些小一点的数),例如:[3, 1, 12, 9, 3, 7, 1, 4, 7, 8, 10]求数组有序后相邻元素之间的最大差值,数组有序后如下:[1, 1, 3, 3, 4, 7, 7, 8, 9, ...
  • 解释: 排序后的数组是 [1,3,6,9], 其中相邻元素 (3,6) (6,9) 之间都存在最大差值 3。 示例 2: 输入: [10] 输出: 0 解释: 数组元素个数小于 2,因此返回 0。 说明: 你可以假设数组中所有元素都...
  • 题目: 给定一个数组数组中相邻的元素之间的差都是d的k倍(1 <= k),求这个d是否存在。若存在,输出d的值;如存在,则输出-1。 思路: 我们可以采用辗转相除法辗转相减法求出最大公约数。 接下来我们用C++...
  • 假设a[0~2]的最大不相邻数组a2用到了最后一个元素,那么a[0~3]的最大不相邻的子数组肯定不是a2+a[3]; 假设a[0~2]的最大不相邻数组a2没有用到最后一个元素,那么a[0~2]等于a[0~1]的最大不相邻数组; ...
  •  1)子数组选择的元素能包含原数组相邻元素  2)满足条件1的前提下,得到的子数组的最大 思路:遍历一次数组,设置两个变量: 包含当前元素的最大值 curMax 包含前一个元素的最大值preMax 在遍历过程过...
  • 提供一个数组,取数组中任意个数相加,但是取的数相邻,输出最后得到的最大值,输入的数组的值均为正整数。 样例 输入:[ 2, 3, 2 ] 输出:4 说明:取第1个值第三个值,2+2 = 4 分析 动态规划。...
  • 题目:给定一个数组,求如果排序之后,相邻两数的最大差值,要求时间复杂度O(N) 例: 数组 arr =[1,3,2,5,8,6] 输出结果:2 看到这个题目我的第一反应是通过多次遍历的这样暴力手段来解决(请原谅我的菜...
  • 求一个数组中非相邻元素最大值问题 视频地址 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...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 119,244
精华内容 47,697
关键字:

数组中不相邻的最大和