Find the Longest Increasing or Decreasing Combination in an Array
Description:
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 integerscommand
: A string representing the ordering of the returned subsequences- Increasing:
"< <"
or"<<"
- Decreasing:
"> >"
or">>"
- Increasing:
Output
- A 2D list (list of lists) of the longest subsequences (length >= 3) of
arr
that are ordered in the way indicated bycommand
.- 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
andcommand = "> >"
, 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]
ofarr
respectively. - Thus, the returned list should be [[-1, -34, -55, -64], [3, -34, -55, -64]]
- For example: if
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]]
Similar Kata:
Stats:
Created | Apr 18, 2016 |
Published | Apr 18, 2016 |
Warriors Trained | 1116 |
Total Skips | 116 |
Total Code Submissions | 2122 |
Total Times Completed | 155 |
Python Completions | 102 |
Ruby Completions | 12 |
JavaScript Completions | 43 |
D Completions | 5 |
Go Completions | 7 |
Rust Completions | 7 |
Haskell Completions | 1 |
Total Stars | 54 |
% of votes with a positive feedback rating | 82% of 51 |
Total "Very Satisfied" Votes | 38 |
Total "Somewhat Satisfied" Votes | 8 |
Total "Not Satisfied" Votes | 5 |
Total Rank Assessments | 3 |
Average Assessed Rank | 5 kyu |
Highest Assessed Rank | 5 kyu |
Lowest Assessed Rank | 5 kyu |