求一个数组的最长递减子序列 比如{9,4,3,2,5,4,3,2}的最长递减子序列为{9,5,4,3,2}

目前想到的一个方法,就是用栈来寻找,说下思想:(栈中的data为元素所在的位置,这意味着出栈和进栈的都是索引值,所以比较的时候根据索引找到其值后比较)

(1)栈为空,把一个元素入栈。9

(2)把小于栈顶的元素依次入栈。9 4 3 2,入栈完成后记录一下该组合

(3)若栈为空,结束,非空,则出栈,寻找小于栈顶值大于出栈值的元素,出栈后当栈为空时,找到一个比弹出元素大的即可。(开始查找的位置出栈值所在位置的后一个)

(4)若找到,则把该元素入栈,跳到步骤(2)

(5)若找不到,则继续步骤(3)

(6)其中组合最大的即为所求

模拟一下该过程

9(1)

9 4 3 2(2)

9 4 3(3)(5)

9 4(3)(5)

9 5(3)(4)

9 5 4 3 2(2)

9 5 4 3 (3)(5)

9 5 4 (3)(5)

9 5(3)(5)

9(3)(5)

(3)(5)

结束

原文地址:https://www.cnblogs.com/GoAhead/p/2525978.html