描述

给定一个长度为$nn$n的数组，选取一些不相邻的数，使得取出的数最大。

思路

• 动态规划的入门题目，设$dp\left[n\right]dp[n]$dp[n]表示仅考虑区间$[1,n][1,n]$[1,n]所能得到的最大结果，对于某个数$ii$i，它可以做的选择为
  • 合入区间$[1,i-1][1,i-1]$[1,i−1]的最优结果当中
  • 仅仅选择它自己
  • 一个数都不选
• 则最终的转移公式为$dp\left[i\right]=max\left(\right\{dp[i-2]+a\left[i\right],a\left[i\right],dp[i-1]\left\}\right);dp[i]=max(\backslash \{dp[i-2]+a[i],a[i],dp[i-1]\backslash \});$dp[i]=max({dp[i−2]+a[i],a[i],dp[i−1]});，最终答案为$dp\left[n\right]dp[n]$dp[n]

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
int a[MAXN];
ll sum[MAXN];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sum[1]=a[1];
    for(int i=2;i<=n;i++)
        sum[i]=max({sum[i-2]+a[i],1LL*a[i],sum[i-1]});
    printf("%lld\n",sum[n]);
}

时间复杂度$O\left(n\right)O(n)$O(n),空间复杂度$O\left(n\right)O(n)$O(n)