这是一个最长上升子序列问题，要求出一串数字最长序列的方法就是对他惊醒比较，然后标记，需要O(n^2)的时间复杂度。
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <string.h>
using namespace std;
#define MAX 100005
int arr[MAX];
int ans[MAX];
int main() {
int x = 0;
arr[0] = 0;
int value = 0;
while (scanf("%d", &arr[++x]) != EOF);
//单纯的求最长长度
//但是数组里面存的值是每个链上每一位出现的最后一位值
for (int i = 1; i < x; i++) {
for (int j = 1; j < x; j++) {
if (ans[j] < arr[i]) {
ans[j] = arr[i];
if (ans[0] < j) ans[0] = j;
break;
}
}
}
value = ans[0], ans[0] = 0;
memset(ans, 0, sizeof(ans));
//求有几条序列
for (int i = 1; i < x; i++) {
ans[i] = 1;
for (int j = 1; j < i; j++) {
if (arr[j] < arr[i]) {
ans[i] = max(ans[i], ans[j] + 1);
}
}
ans[0] = max(ans[0], ans[i]);
}
cout << value << " " << ans[0] << endl;
return 0;
}
