学步园

比如下列数组

最长递增子序列为1, 2, 4, 6,当我们考虑到第i个元素时，当前最大的递增子序列是完全由前一个元素的最大递增子序列确定的，而不管前面的排列是怎样，因此，这个问题满足无后效性，可以用动态规划来实现

LIS[i+1] = max{1, LIS[k] + 1}, array[i+1] > a[k] , k从0到i

#include <iostream>

using namespace std;

int main() {
  int a[8] = {1, -4, 3, -3, -2, -1, 0, 4};
  int LIS[8] = {};
  int f[8] = {};
  int max_index = 0;
  int size, s;

  for (int i = 0; i < 8; i++) {
    LIS[i] = 1;
    for (int j = 0; j < i; j++) {
      if (LIS[i] < LIS[j] + 1 && a[i] > a[j])
        LIS[i] = LIS[j] + 1;
    }
    if (LIS[i] > LIS[max_index])
      max_index = i;

  }
  size = s = LIS[max_index];
  f[--size] = a[max_index];
  for (int j = max_index-1; j >= 0; j--) {
    if (LIS[j]+1 == LIS[max_index]) {
      f[--size] = a[j];
      max_index = j;
    }
  }
  for (int i = 0; i < s; i++)
    cout << f[i] << " ";
  cout << endl;
  return 0;
}