java - 寻找关于如何在我已经有长度的情况下返回最长的非连续子串的提示(不是答案)

Question

我的代码目前返回最大子串的长度:

for(int i = 1; i<=l-1;i++)
{
   counter = 1;

   for(int j = 0; j<i;j++)
   {
      if(seq[j]<seq[j+1])
      {
         count[j] = counter++;    
      }
   }
}
     for(int i = 0;i<l-1;i++)
     {
        if(largest < count[i+1])
        {
           largest = count[i+1];
        }

     }

假设 seq 是序列中的数字。所以如果序列是:5;3;4;8;6;7，它打印出 4。但是，我希望它也打印出 3;4;6;7，这是按升序存在的最长的。

我正在尝试获取最大子序列本身和实际序列的长度，但我已经有了长度.. 我的直觉是将每个数字存储在数组中，同时计算计数。所以返回最长的计数，也可以返回附加到它的数组。我认为这可以用哈希表来完成，但我不确定如何使用它们。

我只是在寻找提示，而不是答案。

谢谢

Answer 1

您需要为 longest ascending subsequence 实现一个动态规划算法.这个想法是为每个位置i存储一对值:

• 在位置 i 结束的最长上升子序列的长度
• 在这样的升序子序列中当前项目之前的项目的索引，或者 -1 如果所有先前的数字都大于或等于当前的数字。

您可以通过将第一对设置为 {Length=1, Prior=-1}、按升序遍历数组并寻找“最佳”前导来轻松构建这两个数组索引 i 处的当前项。前任必须满足这两个条件:

• 它必须具有较低的索引并且小于 i 处的项目，并且
• 它必须结束一个长度大于您目前找到的序列的升序子序列。

以下是数据如何查找您的序列:

Index:        0  1  2  3  4  5
Value:        5  3  4  8  6  7
------------  ----------------
Length:       1  1  2  3  3  4
Predecessor: -1 -1  1  2  2  4

运行完成后，在length 数组中找到最大值，并使用前导索引将其链接回开头，直到达到-1。