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

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

您需要为最长上升子序列实现动态规划算法。这个想法是为每个位置存储一对值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

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