子序列理论与基础算法研究

20/22子序列理论与基础算法研究第一部分子序列理论基础概念概述 2第二部分子序列理论算法类型分析 4第三部分长度最长子序列算法研究 7第四部分最长公共子序列算法讲解 10第五部分最长公共子序列应用场景 12第六部分最长递增子序列算法原理 16第七部分最长递减子序列算法步骤 18第八部分子序列算法复杂度分析 20

第一部分子序列理论基础概念概述关键词关键要点【子序列理论】：

1.子序列是序列的一个连续部分，子序列不一定是连续的。

2.子序列可以是原序列的任意长度的连续部分，也可以是原序列的任意长度的不连续部分。

3.子序列可以是原序列的任意长度的连续部分，也可以是原序列的任意长度的不连续部分。

【最长公共子序列】：

《子序列理论与基础算法研究》——子序列理论基础概念概述

#一、子序列的定义

子序列（Subsequence）是指由原序列中的某些元素组成的序列，这些元素保持其在原序列中的相对顺序。也就是说，子序列中元素的排列顺序与原序列中元素的排列顺序相同。子序列可以是原序列的连续子序列，也可以是非连续子序列。

1.连续子序列：

是指原序列中相邻元素组成的子序列。例如，序列[1,2,3,4,5]的连续子序列有[1,2,3],[2,3,4],[3,4,5]。

2.非连续子序列：

是指原序列中不连续元素组成的子序列。例如，序列[1,2,3,4,5]的非连续子序列有[1,3,5],[2,4],[1,4,5]。

#二、子序列的性质

子序列具有许多有趣的性质，这些性质在算法设计和理论分析中有着广泛的应用。

1.单调性：

子序列可以是单调递增的，也可以是单调递减的。单调递增的子序列是指子序列中每个元素都大于等于前一个元素，单调递减的子序列是指子序列中每个元素都小于等于前一个元素。

2.凸性：

子序列可以是凸的，也可以是凹的。凸子序列是指子序列中每个元素都大于等于前一个元素和后一个元素的平均值，凹子序列是指子序列中每个元素都小于等于前一个元素和后一个元素的平均值。

3.长度：

子序列的长度是指子序列中元素的个数。子序列的长度可以从1到原序列的长度。

4.最长子序列：

最长子序列是指具有特定性质（例如，单调性、凸性、和）的最长子序列。最长子序列问题是一个经典的算法问题，在许多领域都有着广泛的应用。

#三、子序列的应用

子序列理论在算法设计和理论分析中有着广泛的应用，包括：

1.最长公共子序列问题：

给定两个序列A和B，最长公共子序列问题是指寻找A和B的公共子序列中长度最大的子序列。最长公共子序列问题在字符串比较、序列对齐和生物信息学等领域有着广泛的应用。

2.最长递增子序列问题：

给定一个序列A，最长递增子序列问题是指寻找A的递增子序列中长度最大的子序列。最长递增子序列问题在算法设计、优化和运筹学等领域有着广泛的应用。

3.最长凸子序列问题：

给定一个序列A，最长凸子序列问题是指寻找A的凸子序列中长度最大的子序列。最长凸子序列问题在金融、经济和信号处理等领域有着广泛的应用。

4.子序列和问题：

给定一个序列A和一个目标值，子序列和问题是指寻找A的子序列，其元素之和等于目标值。子序列和问题在组合优化、图论和运筹学等领域有着广泛的应用。

#四、小结

子序列理论是计算机科学和数学中一个重要的理论，它在算法设计和理论分析中有着广泛的应用。子序列的概念非常简单，但它却蕴含着许多深奥的性质和应用。子序列理论是一个不断发展的领域，新的算法和理论仍在不断涌现，为解决实际问题提供了新的工具和方法。第二部分子序列理论算法类型分析关键词关键要点子序列理论算法设计原则

1.子序列理论算法设计原则概述：子序列算法最重要的设计原则即最大化子序列值的选取，不同算法根据其特性可通过不同的策略完成最大子序列的确定和输出。

2.子序列理论算法设计原则的策略：子序列理论算法设计原则通常采用贪心策略、动态规划策略、分治策略等策略，通过不断选取最优子序列或者最优子区间的策略，最终获得问题整体的最优解。

3.子序列理论算法设计原则的复杂度分析：子序列理论算法设计原则的复杂度分析主要关注其时间复杂度和空间复杂度，通过分析算法中循环次数、递归次数等因素来评估其时间复杂度，通过分析算法中临时变量、辅助空间等因素来评估其空间复杂度。

子序列理论算法分类

1.子序列理论算法分类概述：子序列理论算法根据其策略和实现方式的不同可分为贪心算法、动态规划算法、分治算法等类型，每种算法都具有其独特的特性和适用场景。

2.子序列理论算法分类的具体类型：子序列理论算法常见的类型包括：贪心算法、动态规划算法、分治算法、回溯算法、分支限界算法等，每种算法都具有其独特的运作方式和解决问题的能力。

3.子序列理论算法分类的适用场景：不同类型的子序列理论算法适用于不同的问题类型，例如贪心算法适用于能够通过贪心策略求得最优解的问题，动态规划算法适用于能够通过动态规划策略求得最优解的问题，分治算法适用于能够通过分治策略求得最优解的问题，回溯算法适用于能够通过回溯策略求得最优解的问题等。一、子序列理论算法类型分析

子序列理论算法类型分析是子序列理论研究的重要组成部分，主要对子序列问题的各种算法进行分类和分析，以揭示不同算法的优缺点和适用范围。子序列算法主要分为以下几类：

1.贪心算法

贪心算法是一种简单而有效的算法设计方法，其基本思想是：在每一个步骤中，都选择最优的局部解，并期望通过一系列局部最优解得到整体最优解。贪心算法适用于子序列问题中目标函数具有单调性或亚单调性的情况，如求最长上升子序列、最长公共子序列等。

2.动态规划算法

动态规划算法是一种解决最优化问题的有效算法，其基本思想是：将问题分解成一系列子问题，然后以自底向上的方式逐层解决这些子问题，最终得到整体最优解。动态规划算法适用于子序列问题中目标函数具有最优子结构和重叠子问题的性质，如求最大连续子序列和、最长公共子序列等。

3.回溯算法

回溯算法是一种解决搜索和优化问题的有效算法，其基本思想是：从问题的所有可行解中选取一个解，然后根据该解扩展出新的可行解，依次类推，直到找到满足约束条件的解或达到目标值。回溯算法适用于子序列问题中可行解空间庞大，难以直接列举所有可行解的情况，如求最优子序列、哈密尔顿回路等。

4.分支定界算法

分支定界算法是一种解决整数规划问题的有效算法，其基本思想是：将问题分解成一系列子问题，并根据子问题的最优解和可行解的界限来约束搜索范围，从而减少搜索空间。分支定界算法适用于子序列问题中目标函数具有整数性且约束条件具有整数性的情况，如求最大权独立集、旅行商问题等。

5.近似算法

近似算法是一种解决NP难问题的有效算法，其基本思想是：在多项式时间内找到一个足够接近最优解的近似解。近似算法适用于子序列问题中目标函数难以计算或搜索空间庞大的情况，如求最优匹配、最大团等。

二、子序列算法的优缺点分析

不同的子序列算法具有不同的优缺点，需要根据具体问题选择合适的算法。以下是对几种常见子序列算法的优缺点分析：

1.贪心算法

*优点：简单易懂，易于实现，时间复杂度较低。

*缺点：可能无法得到最优解，适用于目标函数具有单调性或亚单调性的情况。

2.动态规划算法

*优点：能够找到最优解，适用于目标函数具有最优子结构和重叠子问题的性质。

*缺点：时间复杂度较高，适用于可行解空间较小的情况。

3.回溯算法

*优点：适用于可行解空间庞大，难以直接列举所有可行解的情况。

*缺点：时间复杂度较高，适用于搜索空间较小的情况。

4.分支定界算法

*优点：适用于目标函数具有整数性且约束条件具有整数性的情况。

*缺点：时间复杂度较高，适用于可行解空间较小的情况。

5.近似算法

*优点：能够在多项式时间内找到一个足够接近最优解的近似解。

*缺点：可能无法得到最优解，适用于目标函数难以计算或搜索空间庞大的情况。第三部分长度最长子序列算法研究关键词关键要点动态规划算法在最长子序列中的应用

1.动态规划算法是一种解决最优化问题的经典算法，它可以将问题分解成一系列子问题，然后逐个解决子问题，最后将子问题的解组合成总体最优解。

2.在最长子序列问题中，动态规划算法可以用于求解最长公共子序列（LCS）的长度和最长上升子序列（LIS）的长度。

3.求解LCS问题的经典动态规划算法是Needleman-Wunsch算法。该算法的时间复杂度为O(mn)，其中m和n分别为两个输入序列的长度。

4.求解LIS问题的经典动态规划算法是LongestIncreasingSubsequence(LIS)算法。该算法的时间复杂度为O(n^2)。

贪心算法在最长子序列中的应用

1.贪心算法是一种解决优化问题的启发式算法，它在每一步都选择当前看来最优的方案，而不考虑该方案对整体最优解的影响。

2.在最长子序列问题中，贪心算法可以用于求解最长公共子序列（LCS）的长度和最长上升子序列（LIS）的长度。

3.求解LCS问题的经典贪心算法是LongestCommonSubstring(LCS)算法。该算法的时间复杂度为O(mn)，其中m和n分别为两个输入序列的长度。

4.求解LIS问题的经典贪心算法是LongestIncreasingSubsequence(LIS)算法。该算法的时间复杂度为O(n^2)。长度最长子序列算法研究

在计算机科学中，长度最长子序列（LCS）算法是一种用于查找两个字符串中最长公共子序列（即子序列）的算法。LCS问题在生物信息学、密码学和其他领域有着广泛的应用。

#问题表述

给定两个字符串$X$和$Y$，长度分别为$m$和$n$，LCS问题是找到一个长度最长的子序列$Z$，使得$Z$同时是$X$和$Y$的子序列。

例如，给定字符串$X="ABCDGH"$和$Y="AEDFHR"，LCS为"ADH"，长度为3。

#动态规划算法

最常见的LCS算法是动态规划算法。该算法基于以下递推关系：

其中，$LCS(i,j)$表示字符串$X[0,\dots,i]$和$Y[0,\dots,j]$的LCS的长度。

该算法的时间复杂度为$O(mn)$，其中$m$和$n$分别是字符串$X$和$Y$的长度。

#其他算法

除了动态规划算法之外，还有其他几种LCS算法，包括：

*贪心算法：贪心算法通过在每次迭代中选择最优的局部解来构造LCS。虽然贪心算法通常速度较快，但它并不总是能找到最优解。

*分治算法：分治算法将LCS问题分解成较小的子问题，然后递归地解决这些子问题。分治算法的时间复杂度通常为$O(mn\logmn)$。

*平行算法：平行算法利用多核处理器或分布式计算系统来同时解决LCS问题的多个子问题。平行算法的时间复杂度通常为$O(mn/p)$，其中$p$是处理器或计算节点的数量。

#应用

LCS算法在生物信息学、密码学和其他领域有着广泛的应用。

*生物信息学：LCS算法可用于比较蛋白质或核酸序列，以确定它们的相似性。

*密码学：LCS算法可用于破解密码，通过比较加密文本和已知明文来找到可能的密钥。

*自然语言处理：LCS算法可用于比较文本，以确定它们的相似性或差异性。

#结论

LCS算法是一种用于查找两个字符串中最长公共子序列的算法。LCS问题在生物信息学、密码学和其他领域有着广泛的应用。最常见的LCS算法是动态规划算法，其时间复杂度为$O(mn)$，其中$m$和$n$分别是字符串$X$和$Y$的长度。此外，还有其他几种LCS算法，包括贪心算法、分治算法和平行算法。第四部分最长公共子序列算法讲解关键词关键要点【最长公共子序列识别】：

1.确定两个子序列是否相同：通过判断两个子序列中每个元素的顺序是否相同。

2.子序列的长度：从第一个字符开始，一直到最后一个字符，计算子序列的长度。

3.子序列的识别：通过比较两个子序列的长度和顺序，来确定它们是否相同。

【最长公共子序列建模】：

#最长公共子序列算法讲解

算法基本原理

最长公共子序列（LCS）问题是一个经典的计算机科学问题，其目的是在两个给定序列中找到一个最长的公共子序列。最长公共子序列是指两个序列中共同出现的元素序列，且该序列的元素在两个序列中出现的顺序与在最长公共子序列中出现的顺序相同。

最长公共子序列算法是一种用于求解最长公共子序列问题的动态规划算法。该算法的基本原理是将两个给定序列划分为一系列重叠的子序列，然后递归地求解每个子序列的最长公共子序列。通过这种方式，算法可以逐步地构建出两个序列的最长公共子序列。

算法步骤

最长公共子序列算法的具体步骤如下：

1.创建一个二维数组`L`，其中`L[i][j]`表示第一个序列的前`i`个元素与第二个序列的前`j`个元素的最长公共子序列的长度。

2.将`L[i][0]`和`L[0][j]`初始化为0，表示空序列的最长公共子序列长度为0。

3.对于`i`从1到第一个序列的长度，对于`j`从1到第二个序列的长度，执行以下步骤：

4.如果第一个序列的第`i`个元素与第二个序列的第`j`个元素相等，则`L[i][j]=L[i-1][j-1]+1`。

5.否则，`L[i][j]=max(L[i-1][j],L[i][j-1])`。

6.返回`L[m][n]`，其中`m`和`n`分别为第一个和第二个序列的长度。

算法分析

最长公共子序列算法的时间复杂度为`O(mn)`，其中`m`和`n`分别为第一个和第二个序列的长度。这是因为算法需要遍历两个序列的每个元素，并计算每个元素与另一个序列的每个元素之间的最长公共子序列长度。

最长公共子序列算法的空间复杂度为`O(mn)`。这是因为算法需要使用一个二维数组`L`来存储每个子序列的最长公共子序列长度。

算法应用

最长公共子序列算法有很多实际应用，包括：

*文本编辑：最长公共子序列算法可以用于计算两个文本文件之间的差异。通过找到两个文本文件的最长公共子序列，可以找出两个文本文件之间相同的文本，以及不同的文本。

*序列比较：最长公共子序列算法可以用于比较两个序列的相似性。通过计算两个序列的最长公共子序列的长度，可以衡量两个序列之间的相似程度。

*生物信息学：最长公共子序列算法可以用于比较两个DNA序列或蛋白质序列的相似性。通过计算两个序列的最长公共子序列的长度，可以推断出两个序列之间的进化关系。

最长公共子序列算法是一个强大而通用的算法，它可以用来解决许多实际问题。该算法的时间复杂度和空间复杂度都是`O(mn)`，这使得它适用于处理中等规模的数据集。第五部分最长公共子序列应用场景关键词关键要点自然语言处理

1.最长公共子序列（LCS）在自然语言处理中被广泛用于文本比较、文本挖掘和文本分类。如在文本相似性计算中，LCS可以从文本中提取最相关的公共子序列，并根据匹配程度衡量文本相似程度。

2.LCS还可用于文本摘要，通过提取文本中的最长公共子序列，可以生成精简且保留重要信息的摘要。

3.另外，LCS在机器翻译中也能发挥作用，通过找到源语言和目标语言中的最长公共子序列，可以帮助翻译系统生成更准确的翻译结果。

语音识别

1.在语音识别中，LCS算法可以用于识别语音输入中的单词。通过将语音输入与预先存储的单词序列进行比较，可以找到最长的公共子序列，从而确定输入的单词。

2.LCS还可以用于优化语音识别算法的性能。通过在算法中加入LCS算法，可以提高识别准确率，同时减少计算量。

3.利用LCS算法，可以构建有效的语音识别系统，能够在不同的环境和条件下准确识别语音输入，满足工业和商业的需求。

计算机视觉

1.在计算机视觉中，LCS算法可以用于图像匹配和目标识别。通过将图像分解为子序列，并比较子序列之间的关系，可以找到图像间的相似性，从而进行图像匹配。

2.LCS算法还可以用于目标识别，通过将目标图像与模板图像进行比较，可以找到最长的公共子序列，从而确定目标图像中是否存在对应的目标。

3.此外，LCS算法还可以用于物体检测，通过将检测到的物体与预先存储的物体模板进行比较，可以找到最长的公共子序列，从而确定检测到的物体类型。

生物信息学

1.在生物信息学中，LCS算法可以用于序列比对。通过比较蛋白质或DNA序列，可以找到最长的公共子序列，从而确定序列之间的相似性，并推测生物进化关系。

2.LCS算法还可以用于基因组组装，通过将不同片段的基因序列进行比较，可以找到公共的子序列，并将其拼接起来，从而重组完整的基因组序列。

3.LCS算法在生物信息学中还有广泛的应用，如蛋白质结构预测、药物设计和疾病诊断等。

数据挖掘

1.在数据挖掘中，LCS算法可以用于发现模式和关联。通过将数据序列进行比较，可以找到最长的公共子序列，从而发现数据中的模式和关联。

2.LCS算法还可以用于分类和聚类，通过比较数据点之间的最长公共子序列，可以将数据点分为不同的类别或簇。

3.LCS算法在数据挖掘中还有广泛的应用，如客户关系管理、欺诈检测和网络安全等。

算法设计

1.LCS算法是设计高效算法的范例，体现了动态规划思想，通过将问题分解为子问题，并依次求解子问题，最终得到最优解。

2.LCS算法的复杂度与序列的长度成比例，属于NP完全问题，对于超长序列，直接应用LCS算法计算量过大。因此，需要设计更有效的算法来解决超长序列的最长公共子序列问题。

3.LCS算法启发了众多新型算法的研究，推动了算法领域的发展，如最长公共子串算法、最长公共子结构算法等。1.生物信息学

最长公共子序列（LCS）算法在生物信息学领域被广泛应用于序列比较和序列分析。例如：

*DNA序列比对：LCS算法可以用于比较两个DNA序列，并找到它们之间的最长公共子序列。这有助于识别基因、突变和进化关系。

*蛋白质序列比对：LCS算法可以用于比较两个蛋白质序列，并找到它们之间的最长公共子序列。这有助于识别蛋白质结构、功能和进化关系。

*RNA序列比对：LCS算法可以用于比较两个RNA序列，并找到它们之间的最长公共子序列。这有助于识别RNA结构、功能和进化关系。

2.文本处理

LCS算法在文本处理领域也有着广泛的应用，例如：

*文本比较：LCS算法可以用于比较两个文本，并找到它们之间的最长公共子序列。这有助于识别文本中的相似性和差异性，并用于文本编辑、文本匹配和文本分类等任务。

*文本对齐：LCS算法可以用于对齐两个文本，以便突出它们的差异之处。这有助于文本翻译、文本编辑和文本校对等任务。

*文本压缩：LCS算法可以用于压缩文本，通过只存储文本中的最长公共子序列即可。这有助于减少文本的存储空间，提高文本的传输效率。

3.数据挖掘

LCS算法在数据挖掘领域也有着重要的应用，例如：

*数据比较：LCS算法可以用于比较两个数据集，并找到它们之间的最长公共子序列。这有助于识别数据集中的相似性和差异性，并用于数据聚类、数据分类和数据关联分析等任务。

*数据挖掘：LCS算法可以用于挖掘数据中的模式和规律。这有助于发现数据中的隐藏信息，并用于数据预测、数据异常检测和数据清洗等任务。

4.其他领域

LCS算法在其他领域也有着广泛的应用，例如：

*模式识别：LCS算法可以用于识别模式，例如图像中的物体、语音中的单词和手势中的动作。这有助于构建模式识别系统，用于图像识别、语音识别和手势识别等任务。

*语音合成：LCS算法可以用于合成语音，通过连接字词的最长公共子序列来生成流畅的语音。这有助于构建语音合成系统，用于语音播报、语音导航和语音控制等任务。

*密码学：LCS算法可以用于密码的加密和解密。这有助于构建密码系统，用于保护数据的安全性和隐私性。

总之，LCS算法在生物信息学、文本处理、数据挖掘、模式识别、语音合成和密码学等领域都有着广泛的应用，并且在这些领域发挥着重要的作用。第六部分最长递增子序列算法原理关键词关键要点【最长递增子序列算法的高效实现】:

1.利用动态规划思想构建最长递增子序列的递推关系式，通过递推的方式求出最长递增子序列的长度。

2.使用优化过的算法，如二分查找或线段树，在常数时间内更新最长递增子序列的长度，从而提高算法的效率。

3.利用动态规划思想构建最长递增子序列的回溯路径，可以方便地构造最长递增子序列。

【最长递增子序列算法的空间优化】:

#最长递增子序列算法原理

一、引言

最长递增子序列（LIS）问题是计算机科学中的一个经典问题，它要求找到一个序列中所有元素的递增子序列中最长的一个。该问题有许多应用，例如在计算生物学、模式识别和优化等领域。

二、算法原理

最长递增子序列算法的基本原理是动态规划。动态规划是一种解决优化问题的技术，它将问题分解成更小的子问题，然后逐个求解这些子问题，最后将子问题的解组合起来得到整个问题的解。

在最长递增子序列算法中，子问题是找到序列中以某个元素为结尾的最长递增子序列的长度。我们可以利用以下递推关系来求解子问题：

```

LIS(i)=max(LIS(j)+1)forallj<i,nums[j]<nums[i]

```

其中，LIS(i)表示序列中以元素`nums[i]`为结尾的最长递增子序列的长度。

三、算法步骤

最长递增子序列算法的步骤如下：

1.初始化一个数组LIS，其中LIS[i]存储以元素`nums[i]`为结尾的最长递增子序列的长度。

2.对于序列中的每个元素`nums[i]`,做如下操作：

*找到所有`j<i`且`nums[j]<nums[i]`的元素。

*计算LIS[i]=max(LIS[j]+1)forallj<i,nums[j]<nums[i]。

3.返回LIS[n-1]，其中`n`是序列的长度。

四、算法复杂度

最长递增子序列算法的时间复杂度为`O(n^2)`,其中n是序列的长度。

五、算法应用

最长递增子序列算法有许多实际应用，包括：

*计算生物学：在计算生物学中，最长递增子序列算法可用于找到蛋白质或DNA序列中的保守序列。

*模式识别：在模式识别中，最长递增子序列算法可用于检测图像或语音中的模式。

*优化：在优化中，最长递增子序列算法可用于找到函数的局部最优解。

六、总结

最长递增子序列算法是一种经典的动态规划算法，它可以有效地求解最长递增子序列问题。该算法有许多实际应用，包括计算生物学、模式识别和优化等领域。第七部分最长递减子序列算法步骤关键词关键要点最长递减子序列算法简介

1.最长递减子序列算法用于计算序列中，长度最长的递减子序列。

2.该算法的时间复杂度为O(nlogn)。

3.算法的核心思想是，将序列中的每个元素与之前的所有元素进行比较，如果当前元素小于之前的某个元素，则将其添加到递减子序列中。

最长递减子序列算法步骤

1.初始化一个递减子序列，该子序列的第一个元素是序列中的第一个元素。

2.对于序列中的每个元素x，与递减子序列中的最后一个元素y进行比较。

3.如果x小于y，则将x添加到递减子序列中。

4.否则，从递减子序列中删除y，并用x替换y。

5.重复步骤2-4，直到遍历完整个序列。

6.递减子序列中的元素即为最长递减子序列。

最长递减子序列算法示例

1.给定序列：5,3,4,2,1

2.初始化递减子序列：5

3.与递减子序列中的最后一个元素进行比较：

-3小于5，将其添加到递减子序列中：5,3

-4不小于3，跳过

-2小于4，将其添加到递减子序列中：5,3,2

-1小于2，将其添加到递减子序列中：5,3,2,1

4.最长递减子序列为：5,3,2,1

最长递减子序列算法应用

1.最长递减子序列算法可用于解决多种问题，例如：

-最长公共子序列问题

-最小编辑距离问题

-序列对齐问题

2.最长递减子序列算法在生物信息学、自然语言处理、数据挖掘等领域都有广泛的应用。

最长递减子序列算法优化

1.最长递减子序列算法的时间复杂度为O(nlogn)，可以通过使用动态规划或其他算法来优化复杂度。

2.动态规划算法的时间复杂度为O(n^2)，但它更易于实现。

3.其他优化算法的时间复杂度可以达到O(n)，但它们往往更复杂且难以实现。#《子序列理论与基础算法研究》——最长递减子序列算法步骤

1.定义：

2.算法步骤：

步骤1：初始化：

-令LDS[i]表示以序列中第i个元素结尾的最长递减子序列的长度。（0≤i<n）

-初始化LDS数组，其中LDS[i]=1（0≤i<n）。这表示以序列中每个元素结尾的最长递减子序列都包含该元素本身。

步骤2：动态规划：

-对于序列中每一个元素a[i]（1≤i<n）：

-对于序列中每一个元素a[j]（0≤j<i）：

-如果a[j]>a[i]，则更新LDS[i]=max(LDS[i],LDS[j]+1)

-这表示如果a[j]>a[i]，那么以a[i]结尾的最长递减子序列可以从以a[j]结尾的最长递减子序列得到，长度为LDS[j]+1。

步骤3：回溯