我有一个整数列表,我需要从列表中找到升序整数的最长子集。
例如:[1,2,5,3,6,7,4]
- 最长的子集应该是 SS = [1,2,3,6,7]
。
谁能至少告诉我实现它的主要指南。
最佳答案
longestSubseq( List, Ans ) :-
longestSubseq( List, [], [], Ans ).
longestSubseq( [], Buffer, [], Buffer ) :- !.
longestSubseq( [], _, AnsRevert, Ans ) :-
reverse( AnsRevert, Ans ).
longestSubseq( [H | Tail], [], Longest, Ans ) :-
longestSubseq( Tail, [H], Longest, Ans ).
longestSubseq( [H | Tail], [BufHead | BufTail], Longest, Ans ) :-
BufHead =< H,
longestSubseq( Tail, [H, BufHead | BufTail], Longest, Ans ).
longestSubseq( [H | Tail], Buffer, Longest, Ans ) :-
[BufHead | _ ] = Buffer,
BufHead > H,
length( Longest, LongestLength ),
length( Buffer, BufferLength ),
(
( BufferLength > LongestLength, NewLongest = Buffer )
;
( BufferLength =< LongestLength, NewLongest = Longest )
),
longestSubseq( Tail, [H], NewLongest, Ans ).
我对 gprolog 不是很熟悉,所以它是一个 swi-prolog 代码。
我们得到的是 2 个谓词:longestSubseq/2
和 longestSubseq/4
。
longestSubseq/4
有一个缓冲区(当前单调子序列),最长(当前时间最长的子序列)和一个累加器 Ans。
我们需要在该累加器中处理一些行为:
- 缓冲区为空。我们在其中添加了新元素。
- 新元素小于最后一个缓冲区元素。我们将该元素放入缓冲区。
- 新元素大于最后一个缓冲区元素。我们清除缓冲区并将该元素放入其中。如果缓冲区大于最长的子序列,我们将替换它。
所以,这似乎是可行的。
?- longestSubseq( [2], X ).
X = [2] ;
false.
?- longestSubseq( [2,1,2,3,2], X ).
X = [1, 2, 3] ;
false.
关于prolog - gprolog 最长子集,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8218274/