题解 | #最大上升子序列和# C++ DP 逐步注释

#include "iostream"
#include "vector"
using namespace std;

// 思路：Dp数组问题经典思路-从后往前
// 从倒数第二个元素开始，不断找后面元素比自己的的元素，随后判断：max（自己、dp[比自己大的元素]），作为dp[自己]
// 如:1 7 3 5 9 4 8 起始DP：0 0 0 0 0 0 8
// 4 : 4<8 YES 4+dp=4+8=12 max(4,12) = 12 DP:0 0 0 0 0 12 8
// 9 : 9<4 NO 9<8 NO max(9)=9 DP:0 0 0 0 9 12 8
// 5 : 5<9 YES 5+dp(9)=5+9=14 ; 5<4 NO ; 5<8 YES 5+dp(8)=5+8=13 max(5,14,13)=14 DP:0 0 0 14 9 12 8
// 3 : 3<4 YES 3+dp(5)=3+14=17 ; 3<9 YES 3+dp(9)=12 ; 3<4 YES 3+dp(4)=15 ; 3<8 YES 3+dp(8)=11 max(3,17,12,15,11)=17 DP:0 0 17 14 9 12 8
// 7 : 7<3 NO ; 7<5 NO; 7 < 9 YES 7+dp(9)=16 ; 7<4 NO ; 7<8 YES 7+dp(8)=15 max(7,16,15)=16 DP:0 16 17 14 9 12 8
// 1 : 1<7 YES 1+dp(7)=17; 1<3 YES 1+dp(3)=18 ;1<3,5,9,...(略)	max(1,17,18,15,10,13,9)=18 DP:18 16 17 14 9 12 8
// max(dp)=max(18 16 17 14 9 12 8)=18 结果

// 开始实现：我比较菜，仅限参考
int main() {
	int num;										// 输入数据的个数
	while (cin >> num) {							// 懒狗专属cin
		// define:
		vector<int> dp(num);						// dp 数组
		vector<int> data(num);						// 用于保存输入的数据
		// input & initial:
		for (int i = 0; i < num; i++) cin >> data[i];
		// function:
		int maxDP = dp[num - 1] = data[num - 1];	// dp:初始状态定义 及 保留全局dp最大值（结果）
		for (int i = num - 2; i >= 0; i--) {		// dp:从倒数第二个元素往前遍历
			int maxTempDp = data[i];				// dp:用于保存当前 i 的最大dp值（局部max），即取max过程
			for (int j = i + 1; j < num; j++) 		// dp:逐个检查 i 后面的元素是否比 i 大
				if (data[j] > data[i]) 				// dp:如果比 i 大，存在上升子序列,更新局部DP最大值
					maxTempDp = maxTempDp > dp[j] + data[i] ? maxTempDp : dp[j] + data[i];
			dp[i] = maxTempDp;						// dp:将局部最大DP保存
			maxDP = maxDP > dp[i] ? maxDP : dp[i];	// dp:更新全局DP最大值
		}
		// output:
		cout << maxDP << endl;
	}

	return 0;
}