原题链接: 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 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]);

 

 

 

 

有一个数组：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[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];
    }
}