Codechef:最长的奇异子序列

Question

这个问题可以在http://www.codechef.com/MARCH12/problems/LWS/上找到

这个问题可以使用动态编程来解决。解决这个问题的诀窍是想出一个好的dp状态。我们可以利用这样一个事实，即输入字符串S1..n中仅允许的字符是小写的拉丁字母，即'a‘- 'z’。因此，可以出现的不同字符数不能大于26个。

因此，我们得出以下dp状态: dpkc2 =子串S1..k的LWS的长度，使得非递减子序列以c1结束，而非递增子序列以c2结束。一旦我们确定了状态，我们就可以很容易地得到以下递归:为了计算dpkc2，我们尝试将小写字母Sk添加到非递增或非递减的子序列中，或者不将其添加到任何一个子序列中。

因此，如果c1<=Sk: dpkSk]c2 = max(dpkSk] c2，dpk-1c2+1)，类似地，如果c2>=Sk dpk[Sk] = max(dpk[Sk]，dpk-1c2+1)，则可以通过迭代c1和c2并找到所有dpnc2中的最大值来找到最终答案。我们可以看到，对于从1到n的每个可能长度的子串，我们必须计算26 * 26个状态，其中n是字符串的长度。因此，解的阶数是O(26*26*n)。

然而，当列表中的元素是0到10^6之间的数字时，我们需要解决它时，我陷入了一个困境

Answer 1

在时间和空间之间将会有一个权衡。当序列的元素是介于0和10^6之间的数字时，问题中给出的解决方案将不起作用。

我们知道在O(nLgn)中可以找到最长的递增子序列。让原始序列保存在数组A中。假设有一个数组I，这样in将保存最长递增子序列的长度，直到An。设有一个数组D，使得Dn将保存从an到A结尾的最长递减子序列的长度。现在，您需要找到max(Ik + Dk) - 1。