231testing专题

最长单调递减子序列(非严格单调) uva 231Testing the CATCHER

问题描述: 一个序列seq [],找出一个最长的不严格单调递减的子序列(subseq [i+1] <= subseq [i] ),输出这个子序列的长度 解决1:O(n*n) 令dp [] 数组,dp [i] 表示以seq [i] 为最小元素(也就是子序列中最后一个)的序列的长度,dp []的最大值就是所求结果 伪代码:   int seq[] , dp[]   dp[0]  = 1;