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.这是在升序中存在时间最长的

我试图得到最大子序列本身和实际序列的长度，但我已经有了长度 我的直觉是在计算计数时，将每个数字存储在数组中。因此，返回最长计数也可以返回附加到它的数组。我认为这可以通过哈希表实现，但我不确定如何使用它们

我只是想找个提示，不是答案

谢谢

Answer 1

您需要为longest ascending subsequence实现一个动态规划算法。其思想是为每个位置存储一对值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