5 kyu

Find the Longest Increasing or Decreasing Combination in an Array

102 of 155raulbc777

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 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]]
Data Structures
Algorithms
Mathematics

Stats:

CreatedApr 18, 2016
PublishedApr 18, 2016
Warriors Trained1116
Total Skips116
Total Code Submissions2122
Total Times Completed155
Python Completions102
Ruby Completions12
JavaScript Completions43
D Completions5
Go Completions7
Rust Completions7
Haskell Completions1
Total Stars54
% of votes with a positive feedback rating82% of 51
Total "Very Satisfied" Votes38
Total "Somewhat Satisfied" Votes8
Total "Not Satisfied" Votes5
Total Rank Assessments3
Average Assessed Rank
5 kyu
Highest Assessed Rank
5 kyu
Lowest Assessed Rank
5 kyu
Ad
Contributors
  • raulbc777 Avatar
  • smile67 Avatar
  • Voile Avatar
  • akar-0 Avatar
  • tobeannouncd Avatar
  • saudiGuy Avatar
Ad