DP：最长递增子序列思维过程及解法

Question

对于最长的子序列递增问题，我设想保持一个总是有序的DP数组，将最大值保持在最远端。看起来像这样的东西：

{1, 1, 2, 3, 3, 4, 5, 6, 6, 6}

我得出第一个不正确的解决方案的思路是，我们想从第一个元素开始查看整个数组，计算LIS，然后在数组末尾递增地添加一个值。在执行此操作时，我们将DP数组中的LIS增量计算为旧子数组加上我们添加的新元素的LIS。这意味着在dp数组的索引i处存在长度为i的子数组的LCS值。

更清楚地说

array => {5, 6, 7, 1, 2, 3, 4}
dp    => {1, 2, 3, 3, 3, 3, 4}

2.）对原始输入数组进行排序

3.）遍历已排序数组，每次下一个值（应大于当前值`)出现在原始数组中的当前值之前时，将变量longth递增1。

4.）返回最长

int lengthOfLIS(vector<int>& seq) {
  if (!seq.size()) return 0;
  vector<int> old = seq;

  sort(seq.begin(), seq.end());

  int longest = 1;

  for (int i = 1; i < seq.size(); ++i) {
    if (seq[i] > seq[i-1] && find(old.begin(), old.end(), seq[i]) - old.begin() > find(old.begin(), old.end(), seq[i-1]) - old.begin()) longest++;
  }
  return longest;
}

array => {5, 6, 7, 1, 2, 3}
dp    => {1, 2, 3, 1, 2, 3}

这里，5是递增子序列的最后一个值，前面没有值，所以它的长度必须为1。如果6是递增子序列的最后一个值，我们必须查看它之前的所有值，以确定以6结尾的子序列可以有多长。在它之前只有5个，从而使迄今为止最长的递增子序列为2。继续这样做，然后返回DP数组中的最大值。此解决方案的时间复杂度为O(n^2)，是标准的朴素解决方案。

我很好奇我怎样才能正确地思考这个问题。我想对我的思维过程进行微调，这样我就可以从头开始想出一个最优的解决方案（这至少是我的目标），所以我想知道

1.）这个问题的什么属性应该触发我以不同的方式使用一个DP数组？事后看来，我最初的方法只是简单地等价于保留一个max变量，但即使这样，我也很难看到这个问题的一个属性会触发这样的想法：嘿，我的DP数组中索引I处的一个条目的值应该是以originalarray[I]结尾的递增子序列的长度。我很难看到我应该如何得出这个结果。

2.）是否有可能使我提出的O(nlog(n))解决方案起作用？我知道存在一个O(nlog(n))解决方案，但由于我不能使我的解决方案起作用，我认为我需要朝正确的方向推一下。

Answer 1

我承认，这是一个有趣的问题，我没有确切的答案，但我想我可以给你一个正确的方向。所以是这样的：

在面对这样的困境时，我通常会求助于基础知识。就像在您的例子中一样，了解动态编程的定义。它有两个属性：

1. 重叠子问题
2. 最优子结构。