Kata

Task

Create a function longestComb/LongestComb/longest_comb (case dependent on language, refer to the initial code) that takes a sequence of integers and a method of ordering integers (increasing/decreasing) and returns all of the longest subsequences (with length of at least 3) of the given sequence such that the subsequence elements are ordered according to the given ordering method.

As a reminder, a subsequence is a sequence derived by deleting some or no elements from a given sequence without changing the order of the remaining elements.

For example, given a sequence S = S_1, S_1 ... S_n, the subsequences of S will all be of the form SubS = S_a, S_b ... S_k such that 1 <= a < b < ... < k <= n and

• If the desired order is increasing: S_a < S_b < ... < S_k
• If the desired order is decreasing: S_a > S_b > ... > S_k

Arguments

• arr: An array/list of integers
• command: A string representing the ordering of the returned subsequences
  • Increasing: "< <" or "<<"
  • Decreasing: "> >" or ">>"

Output

• A 2D list (list of lists) of the longest subsequences (length >= 3) of arr that are ordered in the way indicated by command.
  • If only a single valid subsequence is found, return just that list (see examples).
• The returned list should be ordered by the original element indices from arr.
  • For example: if arr = [-1,3,-34,18,-55,60,118,-64 and command = "> >", there are two increasing subsequences of maximal length: [3,-34,-55,-64] and [-1,-34,-55,-64].
  • These subsequences are formed by the indices [1,2,4,7] and [0,2,4,7] of arr respectively.
  • Thus, the returned list should be [[-1, -34, -55, -64], [3, -34, -55, -64]]

Examples

longest_comb([-1, 3, -34, 18, -55, 60, 118, -64], '< <') == [-1, 3, 18, 60, 118]

longest_comb([-1, 3, -34, 18, -55, 60, 118, -64], '> >') == [[-1, -34, -55, -64], [3, -34, -55, -64]]

We may have some cases without any possible subsequences:

longest_comb([-26, 26, -36, 17, 12, 12, -10, -21], "< <") == []

On the other hand we may have cases with many solutions:

longest_comb([-22, 40, -45, -43, -1, 7, 43, -56], "> >") == [[-22, -45, -56], [-22, -43, -56], [40, -45, -56], [40, -43, -56], [40, -1, -56], [40, 7, -56]]