Longest increasing subsequence: Difference between revisions
Content added Content deleted
(→{{header|C}}: +C) |
|||
| Line 10: | Line 10: | ||
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube |
# [http://www.youtube.com/watch?v=4fQJGoeW5VE Dynamic Programming #1: Longest Increasing Subsequence] on Youtube |
||
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]]. |
# An efficient solution can be based on [[wp:Patience sorting|Patience sorting]]. |
||
=={{header|AutoHotkey}}== |
|||
===Dynamic programming === |
|||
<lang AutoHotkey>Lists := [[3,2,6,4,5,1], [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15]] |
|||
for k, v in Lists { |
|||
D := LIS(v) |
|||
MsgBox, % D[D.I].seq |
|||
} |
|||
LIS(L) { |
|||
D := [] |
|||
for i, v in L { |
|||
D[i, "length"] := 1, D[i, "seq"] := v, D[i, "val"] := v |
|||
Loop, % i - 1 { |
|||
if(D[A_Index].val < v && D[A_Index].length + 1 > D[i].length) { |
|||
D[i].length := D[A_Index].length + 1 |
|||
D[i].seq := D[A_Index].seq ", " v |
|||
if (D[i].length > MaxLength) |
|||
MaxLength := D[i].length, D.I := i |
|||
} |
|||
} |
|||
} |
|||
return, D |
|||
}</lang> |
|||
'''Output:''' |
|||
<pre>3, 4, 5 |
|||
0, 4, 6, 9, 13, 15</pre> |
|||
=={{header|C}}== |
=={{header|C}}== |
||