数组中不相邻元素的最大和

今天药忘吃喽~ 2022-08-09 11:46 147阅读 0赞

原题链接: [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;
    }

[Maximum sum such that no two elements are adjacent]: http://www.geeksforgeeks.org/maximum-sum-such-that-no-two-elements-are-adjacent/