精华内容
下载资源
问答
  • 数组中不相邻元素的最大和

    千次阅读 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;
    }
    
    
    展开全文
  • 题目:求数组中不相邻的和的最大值。 例如: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 ...

     题目:求数组中不相邻的数和的最大值。

    例如: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]);

     

     

     

     

    展开全文
  • 找出相加最大的和,选择相邻数组解为 1,4,7,3 为15 题解: b站视频讲解 https://www.bilibili.com/video/BV12W411v7rd?from=search&seid=16185215057279292603 从最后一个来是按照递归思想...

    有一个数组:arr = [1, 2, 4, 1, 7, 8, 3]

    找出相加最大的和,选择的数不能相邻

    该数组解为 1,4,7,3  和为15

    题解:

    b站视频讲解

    https://www.bilibili.com/video/BV12W411v7rd?from=search&seid=16185215057279292603

    从最后一个来是按照递归的思想,动态规划的思想是从数组的第三个元素开始,选或不选,然后求最大值,将值赋给opt数组,如此循环直到arr数组的最后一个,结束,返回opt[-1],即本题答案

    Python:

    import numpy as np
    
    
    def rec_opt(arr, i):  # 递归求解函数
        if i == 0:
            return arr[0]
        elif i == 1:
            return max(arr[0], arr[1])
        else:
            a = rec_opt(arr, i - 2) + arr[i]  # a为选择数组最后一个元素,然后只能选第i-2个元素
            b = rec_opt(arr, i - 1)  # b为不选最后一个元素,所以就选择第i-1个元素
            return max(a, b)
    
    
    def dp_opt(arr):  # 动态规划求解函数
        opt = np.zeros(len(arr))
        opt[0] = arr[0]
        opt[1] = max(arr[0], arr[1])
        for i in range(2, len(arr)):
            a = opt[i - 2] + arr[i]
            b = opt[i - 1]
            opt[i] = max(a, b)
        return opt[len(arr) - 1]
    
    
    arr = [1, 2, 4, 1, 7, 8, 3]
    p = dp_opt(arr)
    q = rec_opt(arr, 6)
    print(p, end='\t')
    print(q)
    
    展开全文
  • 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];
        }
    }
    
    
    
    展开全文
  • 输入一个只含正数的数组,找到数组满足条件的元素的最大和,条件... * 数组中不相邻数字相加最大和 * */ public class DP1 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); Stri
  • LeetCode精讲(0198):计算数组中不相邻组合的最大和(Python) 题目内容 你是一个专业的小偷,计划偷窃沿街的房屋。每间房内都藏有一定的现金,影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统,如果两...
  • 题目描述: 你是一个专业小偷,计划偷窃沿街房屋。每间房内都藏有一定现金,影响你偷窃...我最开始思想就是求一个数组中的奇数与偶数,看哪个比较大,然后没有AC,所以看了评论用动态规划。还没好好理一
  • 如一个数组是这样:[1,4,3,5],那么最后为下标第1个4下标第三个5组成最大值9. 通常在这种情况下,我会以最后一个数值从后往前进行一个推理。以[1,4,3,5]为例,当我们选择5这个数时候,那么它就能选择3而...
  • 中不相邻元素组成的子数组的最大和 a[0~index] max(不相邻元素组成的子数组) a[0] m0 = 1 a[0~1] = a[0,1] m1 = max(m0 , a[1]) = 8 a[0~2] = a[0,1,2] m2 = max( m0 ...
  • Question:给定一个正数数组,找出不相邻元素的子序列的和的最大值。如:2、5、3、9应该返回14(5+9);8、5、3、9、1应该返回17(8+9);5 4 10 100 10 5应该返回110(5+100+5)  要求:输入第一行为长度n , 第二...
  • 不相邻的最大数组和

    千次阅读 2016-05-10 22:02:04
    不相邻的最大子数组问题描述给一个数组,数组元素为不小于零,求和最大的子数组,其中每个元素在原数组中不相邻。解题思路刚拿到题目可能隐约觉得是个dp问题,求前i个元素的最大子数组,但还是有点手足无措,...
  • 题目: 给定一个数组,数组中相邻的元素之间的差都是d的k倍(1 <= k),求这个d是否存在。若存在,输出d的值;如存在,则输出-1。 思路: 我们可以采用辗转相除法辗转相减法求出最大公约数。 接下来我们用C++...
  • 一个无序数组找其子序列构成的和最大,要求子序列中元素在原数组中两两都不相邻: 可以用递归或者循环解决,现有数组arr[暂不舍定数量],最大不相邻数之=maxsum,思路: 1、假如数组只有1 个值,那么maxsum1 = ...
  • 排序后数组中相邻两数的最大

    千次阅读 2016-04-05 12:42:11
    第二次扫描将数组中的数一一映射到n个桶中的某一个,同时更新每个桶中的最大最小值。 第三次扫描,检测相邻的两个非空桶最靠近的两个数的差值得出结果,因为最大差值可能出现在同一个桶中(一共n个桶,n个...
  • 不相邻的最大数组和

    千次阅读 2016-09-14 22:32:59
    问题1:给出一个数组,求出其中一个子集,使得子集中每个元素在原数组中两两都不相邻并使子集的和最大。 解法:对任意一个元素ai ,有两种可能: 选ai ,单选了ai 就不能选ai-1 ;不选ai 那么ai-1 可以选也可以不选,...
  • 遍历arr找到最大值max最小值min。如果arr长度为N,准备N+1个桶,把max单独放在第N+1个桶,[min,max)范围上数放在1~N号桶里,对于1~N号桶中的每一个桶来说,负责区间为(max-min)/N。如果一个数为num,它应
  • 微信公众号介绍:Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容,分享在学习过程中的读书笔记!期待您关注,欢迎一起学习交流进步! 知乎专栏:...
  • 题目: 给定一个整形数组arr,返回排序后的相邻两数的最大差值。 时间复杂度为O(N)。 解答: 如果用排序法实现,其时间复杂度为O(NlogN),而如果利用桶排序的思想(不是桶排序),可以做到O(N),额外空间复杂度为O(N...
  • 动态规划求不相邻的最大数组和

    千次阅读 2014-09-01 16:42:04
    问题:给出一个数组,求出其中一个子集,使得子集中每个元素在原数组中两两都不相邻并使子集的和最大

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 489
精华内容 195
关键字:

数组中不相邻的最大和