算法:线性dp
、LIS
下面的分析完全可以类比 LIS
状态转移方程:dp[i] = max(dp[i], dp[j] + a[i])
(a[j] < a[i],j < i
)
时间复杂度:O(n^2)
状态总个数等于数列总长度N,计算每一个状态需要枚举前i个数,所以总复杂度为O(n^2)
#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int a[N];
int dp[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;++i) cin>>a[i];
for(int i=1;i<=n;++i)
{
dp[i] = a[i];
for(int j=1;j<i;++j)
{
if(a[j]<a[i]) dp[i] = max(dp[i],dp[j]+a[i]);
}
}
int res = -1;
for(int i=1;i<=n;++i)
{
res = max(res,dp[i]);
}
cout<<res<<endl;
return 0;
}