c++,P1024:考虑所求是 最长不降子序列 的 长度

解题思路:

        定义len = 0； 第一个元素进来，我们直接将他收入temp[len++]中；

                                之后， 每一个元素进来前判断，str[i] 是否大于 temp[i];

                                                                                        若大于 直接 temp = temp + str[i];

                                                                                        若小于 说明它不能接在最后一个后面了。那我们就看一下它该接在谁后面。准确的说，并不是接在谁后                                                                                                       面。而是替换掉谁（因为我们所求的时长度而不是序列）； str[i]小于该元素，说明str[i]更让潜                                                                                                        力；

        特别注意的是，在temp.size() > 1时，新进来的元素 若小于全体temp中的元素，则将temp[0]=str[i].

注意事项:

参考代码:

#include<iostream>
#include<string>
using namespace std;

string standard = ""; //定义全局变量，方便在函数中访问；
int size( char temp) { //如标准链为：qwrat  temp为  a ; 则 i=3,return i;
	for (int i = 0; i <= standard.size(); i++) {
		if (temp == standard[i])
			return i;
	}
}

int main() {
	cin >> standard; //标准链
	string str;
	while (cin >> str) {
		string temp;
		temp += str[0];//找到起始位置；
		int len = 0;// 标准链的长度-1；
		for (int i = 1; i < str.size(); i++) {
			if (size(str[i]) >= size(temp[len]) ) { //
				temp = temp + str[i];
				len++;
			}
			else {
				for (int j = len; j >= 0; j--) {
					if (size(str[i]) >= size(temp[j])) {
						temp[j + 1] = str[i];
						break;
					}
					else if (j == 0 && size(str[i]) < size(temp[j]))
						temp[j] = str[i];
				}
			}
		}
		
	    cout <<  len+1;
	}
	return 0;
}