最长回文子串和最长回文子序列

        X = {x1, x2, x3, ..., xn},  满足x1 < x2 < x3 < ... < xn, 即xi < xi+1 (0 <= i <= n-1)

    dp[ii] = dp[jj] + 1;          // if seq[jj] < seq[ii]
    dp[ii] = 1                    // if seq[jj] >= seq[ii]

// Time complexity: n^2
int LIS_n_n(vector<int> &seq, int NN)
{
    /*
     * dp[ii] is the sequence with seq[ii] as its last element
     *  if seq[jj] <= seq[ii] (jj < ii):          dp[ii] = dp[jj] + 1;
     *  else:                                     dp[jj] = 1
     */
    vector<int> dp(NN, 1);
    int longest = 1;
    // Store index sets with LIS, 0 put as default one
    vector<int> index = {0};
    // lis[ii] store the LIS sequence with seq[ii] as its last element
    vector<vector<vector<int> > > lis;

    // Initialize all lis[ii] (0 <= ii < NN) with its seq[ii] firstly
    for (int ii = 0; ii < NN; ii++) {
        vector<vector<int> > tmp = { {seq[ii]} };
        lis.push_back(tmp);
    }

    for (int ii = 1; ii < NN; ii++) {
        for (int jj = 0; jj < ii; jj++) {
            if (seq[ii] > seq[jj]) {
                if (dp[ii] < dp[jj] + 1) {
                    dp[ii] = dp[jj] + 1;
                    
                    // Clear existing sequence in lis[ii], as longer one appear.
                    lis[ii].clear();        
                    vector<vector<int> > local;
                    local.assign(lis[jj].begin(), lis[jj].end());
                    for (unsigned int kk = 0; kk < local.size(); kk++) {
                        local[kk].push_back(seq[ii]);
                        lis[ii].push_back(local[kk]);
                    }
                } else if (dp[ii] == dp[jj] + 1) {
                    vector<vector<int> > local;
                    local.assign(lis[jj].begin(), lis[jj].end());
                    for (unsigned int kk = 0; kk < local.size(); kk++) {
                        local[kk].push_back(seq[ii]);
                        lis[ii].push_back(local[kk]);
                    }
                }
            }
        }
        if (longest < dp[ii]) {
            longest = dp[ii];
            index.clear();
            index.push_back(ii);
        } else if (longest == dp[ii]){
            index.push_back(ii);
        }
    }

    printf("Longest Increasing Sequences are:\n");
    for (unsigned int ii = 0; ii < index.size(); ii++) {
        int idx = index[ii];
        for (unsigned int jj = 0; jj < lis[idx].size(); jj++) {
            for (unsigned int kk = 0; kk < lis[idx][jj].size(); kk++) {
                if (kk != 0)
                    printf(" ");
                printf("%d", lis[idx][jj][kk]);
            }
            printf("\n");
        }
    }

    return longest;
}

    对于一个上升子序列，其结尾元素越小，越有利于在后面接其他的元素，上升序列变得更长的可能性就越大。  

// Time complexity: n*log(n)
int LIS_n_log_n(vector<int> &seq, int NN)
{
    /*
     * tail[ii] is the minimum value of last element in sequence which length is ii.
     * cc[ii] is the related position of element seq[ii] in LNDS
     *
     *  if seq[ii] > tail[len] :                                     tail[++len] = seq[ii];
     *  else: find first value of tail which isn't smaller than seq[ii], replace with seq[ii]      tail[jj] = seq[ii]
     *  Could also think:   from the last value of tail which is equal to seq[ii], use it to update the next one.
     */
    vector<int> tail(NN + 1);
    vector<int> cc(NN + 1);
    int len = 1;
    tail[len] = seq[0];
    cc[0] = len;

    for (int ii = 1; ii < NN; ii++) {
        if (seq[ii] > tail[len]) {
            tail[++len] = seq[ii];
            cc[ii] = len;
        } else {
            int idx = lower_bound(tail.begin() + 1, tail.begin() + len + 1, seq[ii]) - tail.begin();
            tail[idx] = seq[ii];
            cc[ii] = idx;
        }
    }

    stack<int> output;
    int jj = len;
    for (int ii = NN - 1; ii >= 0; ii--) {
        if (cc[ii] == jj) {
            output.push(seq[ii]);
            jj--;
        }
        if (0 == jj)
            break;
    }
    while (!output.empty()) {
        int top = output.top();
        printf("%d ", top);
        output.pop();
    }

    return len;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int LNDS_n_n(vector<int> &given, int NN, vector<int> &colors)
{
    int longest = 1;
    vector<int> dp(NN, 1);

    for (int ii = 1; ii < NN; ii++) {
        for (int jj = 0; jj < ii; jj++) {
            if (given[jj] <= given[ii]) {
                dp[ii] = max(dp[ii], dp[jj] + 1);
            }
        }
        longest = max(longest, dp[ii]);
    }

    return longest;
}
int main(void)
{
    int NN = 0, MM = 0, LL = 0;
    scanf("%d", &NN);
    // Store whether a color is Eva's favorite or not, presence[ii] == 1 means color ii is valid.
    vector<int> presence(NN+1);
    // Store order of favorite color, order[ii] = 0 means color ii is most favorite one.
    vector<int> order(NN+1);
    vector<int> colors;
    scanf("%d", &MM);

    int color = 0;
    for (int ii = 0; ii < MM; ii++) {
        scanf("%d", &color);
        presence[color] = 1;
        order[color] = ii;
        colors.push_back(color);
    }
    scanf("%d", &LL);
    vector<int> given;
    for (int ii = 0; ii < LL; ii++) {
        scanf("%d", &color);
        if (1 == presence[color])
            given.push_back(order[color]);
    }
    printf("%d\n", LNDS_n_n(given, given.size(), colors));

    return 0;
}