# 最长的后续序列

           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  1  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j     i


if Item[i] > Item[j]
dp[i] := dp[j] + 1


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j     i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j           i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j     i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j                 i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j           i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  1  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j     i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  1  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j                       i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  2  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j                 i


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  3  |  1  |  1  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j           i


if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1


           3     4    -1     0     6     2     3
+-------+-----+-----+-----+-----+-----+-----+-----+
| Index |  0  |  1  |  2  |  3  |  4  |  5  |  6  |
+-------+-----+-----+-----+-----+-----+-----+-----+
| Value |  1  |  2  |  1  |  2  |  3  |  3  |  4  |
+-------+-----+-----+-----+-----+-----+-----+-----+
j     i


Procedure LISLength(Item):
n := Item.length
dp[] := new Array(n)
for i from 0  to n
dp[i] := 1
end for
for i from 1 to n
for j from 0 to i
if Item[i]>Item[j] and dp[i]<dp[j] + 1
dp[i] := dp[j] + 1
end if
end for
end for
l := -1
for i from 0 to n
l := max(l, dp[i])
end for
Return l


Procedure LIS(Item, dp, maxLength):
i := Item.length
while dp[i] is not equal to maxLength
i := i - 1
end while
s = new Stack()
s.push(Item[i])
maxLength := maxLength - 1
current := Item[i]
while maxLength is not equal to 0
i := i-1
if dp[i] := maxLength and Item[i] < current
current := Item[i]
s.push(current)
maxLength := maxLength - 1
end if
end while
while s is not empty
x := s.pop
Print(s)
end while