如何使用动态规划确定最长递增子序列?

问题描述

我有一组整数.我想使用动态规划找到该集合的最长递增子序列.

I have a set of integers. I want to find the longest increasing subsequence of that set using dynamic programming.

推荐答案

好的，我将首先描述最简单的解决方案，即 O(N^2)，其中 N 是集合的大小.还有一个 O(N log N) 解决方案，我也会描述.查看此处的高效算法部分.

OK, I will describe first the simplest solution which is O(N^2), where N is the size of the collection. There also exists a O(N log N) solution, which I will describe also. Look here for it at the section Efficient algorithms.

我将假设数组的索引是从 0 到 N - 1.所以让我们定义 DP[i] 为以元素结尾的 LIS(最长递增子序列)的长度与索引 i.为了计算 DP[i]，我们查看所有索引 j 并检查两者是否 DP[j] + 1 >DP[i] 和 array[j] (我们希望它增加).如果这是真的，我们可以更新 DP[i] 的当前最优值.要找到数组的全局最优值，您可以从 DP[0...N - 1] 中取最大值.

I will assume the indices of the array are from 0 to N - 1. So let's define DP[i] to be the length of the LIS (Longest increasing subsequence) which is ending at element with index i. To compute DP[i] we look at all indices j < i and check both if DP[j] + 1 > DP[i] and array[j] < array[i] (we want it to be increasing). If this is true we can update the current optimum for DP[i]. To find the global optimum for the array you can take the maximum value from DP[0...N - 1].

int maxLength = 1, bestEnd = 0;
DP[0] = 1;
prev[0] = -1;

for (int i = 1; i < N; i++)
{
   DP[i] = 1;
   prev[i] = -1;

   for (int j = i - 1; j >= 0; j--)
      if (DP[j] + 1 > DP[i] && array[j] < array[i])
      {
         DP[i] = DP[j] + 1;
         prev[i] = j;
      }

   if (DP[i] > maxLength)
   {
      bestEnd = i;
      maxLength = DP[i];
   }
}

我使用数组 prev 以便以后能够找到实际序列，而不仅仅是它的长度.只需使用 prev[bestEnd] 在循环中从 bestEnd 递归返回.-1 值是停止的标志.

I use the array prev to be able later to find the actual sequence not only its length. Just go back recursively from bestEnd in a loop using prev[bestEnd]. The -1 value is a sign to stop.

让 S[pos] 定义为结束长度为 pos 的递增序列的最小整数.现在遍历输入集的每个整数 X 并执行以下操作:

Let S[pos] be defined as the smallest integer that ends an increasing sequence of length pos. Now iterate through every integer X of the input set and do the following:

1. 如果 X >S 中的最后一个元素，然后将 X 附加到 S 的末尾.这实质上意味着我们发现了一个新的最大的LIS.

1. If X > last element in S, then append X to the end of S. This essentially means we have found a new largest LIS.

否则找出S中最小的元素，即>=而不是X，改成X.由于 S 是随时排序的，所以可以在 log(N) 中使用二分查找找到该元素.

Otherwise find the smallest element in S, which is >= than X, and change it to X.Because S is sorted at any time, the element can be found using binary search in log(N).

总运行时间 - N 个整数和对每个整数的二分搜索 - N * log(N) = O(N log N)

Total runtime - N integers and a binary search for each of them - N * log(N) = O(N log N)

现在让我们做一个真实的例子:

Now let's do a real example:

整数集合:2 6 3 4 1 2 9 5 8

步骤:

0. S = {} - Initialize S to the empty set
1. S = {2} - New largest LIS
2. S = {2, 6} - New largest LIS
3. S = {2, 3} - Changed 6 to 3
4. S = {2, 3, 4} - New largest LIS
5. S = {1, 3, 4} - Changed 2 to 1
6. S = {1, 2, 4} - Changed 3 to 2
7. S = {1, 2, 4, 9} - New largest LIS
8. S = {1, 2, 4, 5} - Changed 9 to 5
9. S = {1, 2, 4, 5, 8} - New largest LIS

所以LIS的长度是5(S的大小).

So the length of the LIS is 5 (the size of S).

为了重建实际的LIS，我们将再次使用父数组.让 parent[i] 成为 LIS 中索引为 i 的元素的前驱，以索引为 i.

To reconstruct the actual LIS we will again use a parent array.Let parent[i] be the predecessor of an element with index i in the LIS ending at the element with index i.

为了简单起见，我们可以在数组 S 中保存实际的整数，而不是它们在集合中的索引(位置).我们不保留{1, 2, 4, 5, 8}，而是保留{4, 5, 3, 7, 8}.

To make things simpler, we can keep in the array S, not the actual integers, but their indices(positions) in the set. We do not keep {1, 2, 4, 5, 8}, but keep {4, 5, 3, 7, 8}.

即 input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5，输入[8] = 8.

That is input[4] = 1, input[5] = 2, input[3] = 4, input[7] = 5, input[8] = 8.

如果我们正确更新父数组，实际的 LIS 是:

If we update properly the parent array, the actual LIS is:

input[S[lastElementOfS]], 
input[parent[S[lastElementOfS]]],
input[parent[parent[S[lastElementOfS]]]],
........................................

现在重要的是 - 我们如何更新父数组?有两种选择:

Now to the important thing - how do we update the parent array? There are two options:

1. 如果 X >S 中的最后一个元素，然后 parent[indexX] = indexLastElement.这意味着最新元素的父元素是最后一个元素.我们只是在 S 的末尾添加 X.

1. If X > last element in S, then parent[indexX] = indexLastElement. This means the parent of the newest element is the last element. We just prepend X to the end of S.

否则找出S中最小元素的索引，即>=而不是X，改成X.这里parent[indexX] = S[index - 1].

Otherwise find the index of the smallest element in S, which is >= than X, and change it to X. Here parent[indexX] = S[index - 1].

这篇关于如何使用动态规划确定最长递增子序列?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！