最长上升子序列

• 要在能求出答案的基础上让维数最小。因为维数越大则事件复杂度越高。

• f[i] 表示以第 i 个数为结尾的最大长度。集合是所有以第 i 个数结尾的上升子序列

• 

f[i] 的集合里面的元素是： 以下标为0的元素为最后一个元素的序列，以下标为1的元素为最后一个元素的序列.....以下标为i-1的元素为最后一个元素的序列 。当然有一些不存在，因为可能 a[i] < a[j] 。

• 可见，因为状态数量为n，转移的数量也为n（算每个f[i]的时候都要枚举0~i-1）。因此这个算法的事件复杂度为 状态数量 * 计算每个状态需要的时间 = 0(n ^ 2) 。

• 如果想要把最长子序列输出出来的话，可以每次进行状态转移的时候记录下 以当前元素为最后一个元素的最长子序列的前一个元素 。也就是加上一个 g[] 数组， g[i] = j 表示 以i为最后一个元素的最长子序列的前一个元素是第j个元素 。以下为输出最长子序列的所有元素的具体代码

  #include <stdio.h>

  #include <iostream>

  using namespace std;

  const int N = 1010;
  int a[N], f[N], g[N], n;

  int main()
  {
      cin >> n;
      for (int i = 1; i <= n; i++)
          cin >> a[i];

      for (int i = 1; i <= n; i++)
      {
          f[i] = 1;
        g[i] = 1;
          for (int j = 1; j < i; j++)
          {
              if (a[i] <= a[j])
                  continue;
              // 如果需要进行状态转移
              if (f[i] < f[j] + 1)
              {
                  f[i] = f[j] + 1;  // 状态转移
                  g[i] = j;         // 记录上一个元素
              }
          }
      }

      int k = 1;
      for (int i = 1; i <= n; i++)
          if (f[i] > f[k])
              k = i;

      // cout << f[k] << endl;
      do
      {
        printf("%d ", a[k]);
        k = g[k];
      } while (k != 1);

      return 0;
  }