来一个记忆化搜索

dp有四个步骤：
1.重述问题
2.找到最后一步
3.找到最后一步
4.开始递推

初学的人可以先从简单的dfs开始写，再改成记忆化搜索，最后改成递推，这里就到记忆化搜索。

首先是简单的dfs
我们先从1遍历到N ， 那么很明显边界就是x>N，到了边界就选不下去了；
其次加入了a[x]的数列不是上升子序列也不能选；
最后对于任意一个a[x]有选和不选两种状态；
因此简单的dfs就出来了

int dfs(int x,int end)//x:当前选的数 end:上升子序列的末尾
{
	if(x > N) return 0;
	else if(a[x] < end) return dfs(x+1 , end);
	else return max(dfs(x+1 , end) , dfs(x+1 , a[x]) + a[x]);
}

这样的复杂度是指数级的，很明显过不了，因此我们需要升级为记忆化搜索。
开一个记忆数组f，只要f[x][end]不为零说明这条路已经走过了，直接返回。
如果没走过，那么就把当前的值记录一下。

很容易有了以下的代码:

int f[1010][10010];
int dfs(int x,int end)
{
	if(x > N) return 0;
	if(f[x][end]) return f[x][end];
	
	int sum = 0;
	
	if(a[x] < end) sum =  dfs(x+1 , end);
	else sum =  max(dfs(x+1 , end) , dfs(x+1 , a[x]) + a[x]);
	f[x][end] = sum;
	return sum;
}

AC Code

#include <iostream>
using namespace std;

int N;
int a[1010];
int f[1010][10010];
int dfs(int x,int end)
{
	if(x > N) return 0;
	else if(a[x] < end) return dfs(x+1 , end);
	else return max(dfs(x+1 , end) , dfs(x+1 , a[x]) + a[x]);
}
int main()
{
	cin >> N;
	for(int i =1;i<=N;i++) cin >> a[i];
	
	int res =dfs(1 , 0);
	
	cout << res;
	return 0;
}