I'm guessing you mean longest subsequence.

EN
I'm guessing you mean longest subsequence.

Posted October 10th, 2019
by EN

Here's my (uncommented) Python solution. Probably can be improved (possibly by using sets to check if the subsequence should be extended or not) but pretty sure it's O(n).
https://pastebin.com/MDcaGgiA

EN
Here's my (uncommented) Python solution. Probably can be improved (possibly by using sets to check if the subsequence should be extended or not) but pretty sure it's O(n).

https://pastebin.com/MDcaGgiA
Edited October 12th, 2019
by EN

How it works is that it takes the first two elements of the sequence, which is guaranteed to be a valid subsequence, and calls that your maximal subsequence. Then moves does the sequence element by element to create the current subsequence. If the element it sees is the same, it gets added to the current subsequence. If not, the current sequence starts over with the new element as the last element in the current subsequence and the next most recent element that was different as the first element. If the current subsequence is ever longer than the maximal subsequence, call it the maximal subsequence. Basically, keep taking valid subsequences and ask yourself if it's longer than any valid ones you've seen so far.

EN
How it works is that it takes the first two elements of the sequence, which is guaranteed to be a valid subsequence, and calls that your maximal subsequence. Then moves does the sequence element by element to create the current subsequence. If the element it sees is the same, it gets added to the current subsequence. If not, the current sequence starts over with the new element as the last element in the current subsequence and the next most recent element that was different as the first element. If the current subsequence is ever longer than the maximal subsequence, call it the maximal subsequence. Basically, keep taking valid subsequences and ask yourself if it's longer than any valid ones you've seen so far.

Posted October 12th, 2019
by EN