求数组不相邻元素之和的最大值
题目描述
给定一个长度为n的数组，从其中任意选择不相邻的m个元素形成子数组，求这个子数组所有元素之和的最大值。
关于输入
输入包括两行。
第一行为一个正整数n(0<=n<=10000)。
第二行为n个整数，表示整个数组。
关于输出
输出一个数字，代表数组所有不相邻元素之和的最大值。
例子输入
5 1 2 3 4 5
例子输出
9
解题思路
这个程序是用来解决“求数组不相邻元素之和的最大值”问题的。它使用了动态规划的思想。
这个问题的具体描述是：给定一个长度为n的数组，从其中任意选择不相邻的元素形成子数组，求这个子数组所有元素之和的最大值。
程序的主要思路如下：
-
首先，程序读取一个整数n，然后读取n个整数，存储在数组
num中。 -
然后，程序初始化一个二维数组
dp，dp[i][j]表示从i到j（包括i和j）的子数组中，所有不相邻元素之和的最大值。 -
程序遍历所有可能的子数组长度（从1到n）。对于每一个子数组长度，程序遍历所有可能的子数组的起始位置。
-
如果子数组长度为1，那么
dp[i][j]就等于num[i]，因为子数组只有一个元素。 -
如果子数组长度大于1，但是结束位置
j小于2，那么dp[i][j]就等于num[i]和num[j]中的较大值，因为子数组只有两个元素。 -
如果子数组长度大于2，那么
dp[i][j]就等于dp[i][j-2] + num[j]和dp[i][j-1]中的较大值。这是因为，如果选择了j位置的元素，那么j-1位置的元素就不能选择，所以最大和就是dp[i][j-2] + num[j]；如果不选择j位置的元素，那么最大和就是dp[i][j-1]。
-
-
最后，
dp[0][n-1]就是整个数组中，所有不相邻元素之和的最大值。
这个程序的时间复杂度是O(n^2)，因为它需要遍历所有可能的子数组。如果数组的大小非常大，那么这个程序可能会运行得比较慢。
#include <iostream>
using namespace std;
int num[10001];
int dp[10001][10001];
int main() {
int n; cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
for(int len=1;len<=n;len++){
for(int i=0;i<n;i++){
int j=i+len-1;
if(len==1){
dp[i][j]=num[i];
}
else if(j<2){
if(j==1){
dp[i][j]=max(num[i],num[j]);
}
}
else{
dp[i][j]=max(dp[i][j-2]+num[j],dp[i][j-1]);
}
}
}
cout<<dp[0][n-1]<<endl;
return 0;
}
进一步的优化
这个问题实际上可以使用一维动态规划来解决，这样可以将时间复杂度从O(n2)O(n2)降低到O(n)O(n)。
我们只需要一个一维的dp数组，dp[i]表示考虑到第i个元素时，所有不相邻元素之和的最大值。
对于每个元素，我们有两个选择：选择这个元素，或者不选择这个元素。
-
如果我们选择这个元素，那么我们不能选择前一个元素，所以最大和就是
dp[i-2] + num[i]。 -
如果我们不选择这个元素，那么最大和就是
dp[i-1]。
所以，dp[i]就等于上述两个值中的较大值。
#include <iostream>
#include <algorithm>
using namespace std;
int num[10001];
int dp[10001];
int main() {
int n; cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
dp[0] = num[0];
dp[1] = max(num[0], num[1]);
for(int i=2;i<n;i++){
dp[i] = max(dp[i-2] + num[i], dp[i-1]);
}
cout<<dp[n-1]<<endl;
return 0;
}
用记忆搜索法加递归解决本问题！
#include <iostream>
#include <algorithm>
using namespace std;
int num[10001];
int dp[10001]={0};
int getmax(int n){
if(dp[n]) return dp[n];
if(n==0) return num[0];
if(n==1) return max(num[0],num[1]);
dp[n]=max(getmax(n-1),getmax(n-2)+num[n]);
return dp[n];
}
int main() {
int n; cin>>n;
for(int i=0;i<n;i++){
cin>>num[i];
}
cout<<getmax(n)<<endl;
return 0;
}
