31 lines
1.1 KiB
Text
31 lines
1.1 KiB
Text
# Return a list - just one in the case of a tie
|
|
create or replace function longest_increasing_subsequence(lst) as (
|
|
|
|
-- Add a flag to signal the start of a new subsequence
|
|
with flagged as (
|
|
select *, if(id = 1, 0, if(c > (lag(c) over ()), 0, 1)) as flag
|
|
from (select generate_subscripts(lst,1) as id,
|
|
unnest(lst) as c)
|
|
),
|
|
partitions as (
|
|
select *, sum(flag) over (order by id) as partition_number
|
|
from (select *, if(id=1 or (c > (lag(c) over ())), 1, 0) as flag
|
|
from flagged)
|
|
order by id asc
|
|
),
|
|
subseq_number as (
|
|
select max_by(partition_number, ncount) as n
|
|
from (select partition_number, count(*) as ncount
|
|
from partitions
|
|
group by partition_number)
|
|
)
|
|
select array_agg(c order by id)
|
|
from partitions, subseq_number
|
|
where partition_number = subseq_number.n
|
|
);
|
|
|
|
# Examples;
|
|
select l as list, longest_increasing_subsequence(l) as lis
|
|
from (select [3,2,6,4,5,1] as l union all
|
|
select [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15] as l union all
|
|
select [0,8,4,12,2,10,6,14,1,9,5,13,3,11,7,15,20] as l);
|