P1020导弹拦截（最长上升子序列）

这是一个最长上升子序列问题，要求出一串数字最长序列的方法就是对他惊醒比较，然后标记，需要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;
}