数组中不相邻元素的最大和
原题链接: 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;
}
还没有评论,来说两句吧...