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

今天药忘吃喽~ 2022-08-09 11:46 236阅读 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 (元素不能相邻)

  1. arr[] = {
  2. 5, 5, 10, 40, 50, 35}
  3. 1) arr[0] = 5
  4. incl = 5
  5. excl = 0
  6. 2) arr[1] = 5
  7. incl = (excl + arr[1]) = 5
  8. excl = max(5, 0) = 5
  9. 3) arr[2] = 10
  10. incl = (excl + arr[2]) = 15
  11. excl = max(5, 5) = 5
  12. 4) arr[3] = 40
  13. incl = (excl + arr[3]) = 45
  14. excl = max(5, 15) = 15
  15. 5) arr[4] = 50
  16. incl = (excl + arr[4]) = 65
  17. excl = max(15, 45) = 45
  18. 5) arr[5] = 35
  19. incl = (excl + arr[5]) = 80
  20. excl = max(45, 65) = 65
  21. answer is max(incl, excl) = 80

代码

  1. #include <iostream>
  2. using namespace std;
  3. int maxSum(int *arr, int size)
  4. {
  5. if(size<=0)
  6. return 0;
  7. else if(size ==1)
  8. return arr[0];
  9. int excl = 0, incl = arr[0];
  10. int excl_new;
  11. for(int i = 1; i<size; ++i)
  12. {
  13. excl_new = (excl>incl)?excl:incl;
  14. incl = excl + arr[i];
  15. excl = excl_new;
  16. }
  17. return (incl>excl)?incl:excl;
  18. }
  19. int main()
  20. {
  21. int array[] = {
  22. 5,5,10,40,50,35};
  23. cout<<maxSum(array, 6)<<endl;
  24. }

发表评论

表情:
评论列表 (有 0 条评论,236人围观)

还没有评论,来说两句吧...

相关阅读