最大上升子序列和

题目概述：给定一个序列，求解该序列的最大上升子序列的和
解题思路：我们在LIS的集合定义为：以i结尾的上升子序列的最大长度，那其实我们只需要将集合定义改为：以i结尾的上升子序列的最大和即可。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
const int N = 5010;

int num[N];
int f[N];

void solve(){
	int n;
	cin >> n;

	for(int i = 0; i < n; i ++){
		int a;
		cin >> a;
		num[i] = a;
	}

	int res = 0;
	for(int i = 0; i < n; i ++){
		f[i] = num[i];
		for(int j = 0; j < i; j ++){
			if(num[j] < num[i])f[i] = max(f[i],f[j] + num[i]);
		}

		res = max(res,f[i]);
	}
	

	cout << res << endl;
}

int main(){
	int T = 1;

	while(T --){
		solve();
	}
	
}