You must solve it with O(n^2). (This is could be equal with the length of LIS, such as "13245")
Asked
Active
Viewed 121 times
-2
-
Is there a reason why it won't simply be the length of the LIS minus 1? – A. Sarid Sep 25 '16 at 14:09
-
Well, the answer of "13245" is 4, same with the length of LIS. – PythonYXY Sep 25 '16 at 14:10
-
So its not second longest. It's equal or less, so the question is actually to check if there exist another increasing subsequence of same size as the longest. If not the answer will be LIS-1. – A. Sarid Sep 25 '16 at 14:13
-
I thought it would be harder, thanks a lot! – PythonYXY Sep 25 '16 at 14:20
1 Answers
0
This problem can be reduces to:
Check if there exist two or more different LIS's (with the same maximum length of course).
If the answer is yes - the "second"-LIS is obviously the same length as the LIS.
If the answer is no - the second-LIS length is the length of the longest one minus 1.
In order to find the number of LIS's you can simply modify the O(n^2) algorithm described here to keep track of not only the maximum length but also the number of those maximums.
