题目
对于一个给定的数组，在其中选取其子数组，要求相邻的元素不能选取，且要保证选出的子数组元素和最大。输入数组长度及其元素，输出所选子数组的和。
测试输入
7
4 2 6 1 3 5 8
测试输出
21
dp[i]代表到截至第i项的最大和(可能不包括第i项)
分析：对于任何一个dp问题，其都牵扯到选与不选某个元素的问题，当你选择a[i]作为最大和的一部分的时候，最大和就是dp[i-2]+a[i],如果不选择a[i],那么最大和就是到dp[i-1];
所以真正的最大和就是以上两种情况进行比较选择最大的。
代码如下：
#include <bits/stdc++.h> using namespace std; int dp[100];//dp[i]代表到截至第i项的最大和(可能不包括第i项) int main(){ int a[]={4 ,2 ,6 ,1, 3 ,5 ,8}; int i; dp[0]=a[0]; dp[1]=max(a[0],a[1]); for(i=2;i<7;i++){ dp[i]=max(dp[i-2]+a[i],dp[i-1]); }cout<<dp[6]; return 0; }
原文链接: https://www.cnblogs.com/cstdio1/p/11303572.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/300367
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
