POJ2533

求最长递增子序列
原题链接 

一道经典的动态规划题目，思路很简单。
可以考虑以第i个数字结尾的最长子串：length[i] = max{length[j] && seq[j] < seq[i]} + 1, for j = 0 ... i-1
这样时间复杂度为O(N^2)

在原题的基础上，我又加入了可以输出一个最长子串的功能，呵呵，只是为了好玩。但是直接提交肯定会WRONG ANSWER

上代码:

#include <iostream>

using namespace std;

#define MAX 1000

int size;
int seq[MAX];
int trace[MAX];
int length[MAX];
int endPos;

int maxIncSubseq() {
    int maxLength = 1;
    endPos = 0;
    trace[0] = -1;
    length[0] = 1;

    for (int i=1; i<size; i++) {
        int curMax = 0;
        for (int j=0; j<i; j++) {
            if (seq[i] > seq[j] && length[j]+1 > curMax) {
                curMax = length[j] + 1;
                trace[i] = j;
            }
        }
        length[i] = curMax;
        if (curMax > maxLength) {
            maxLength = curMax;
            endPos = i;
        }
    }

    return maxLength;
}

void printSeq(int pos) {
    if(trace[pos] == -1) {
        cout << seq[pos];
        return;
    }
    printSeq(trace[pos]);
    cout << " " << seq[pos];
}

int main() {
    while (cin >> size) {
        for (int i=0; i<size; i++)
            cin >> seq[i];
        cout << maxIncSubseq() << endl;
        printSeq(endPos);
        cout << endl;
    }
    return 0;
}