One goes up, the other comes down

Question

Introduction

In this challenge, your task is to decide whether a given sequence of numbers can be separated into two subsequences, one of which is increasing, and the other decreasing. As an example, consider the sequence 8 3 5 5 4 12 3. It can be broken into two subsequences as follows:

  3 5 5   12
8       4    3

The subsequence on the first row is increasing, and the one on the second row is decreasing. Furthermore, you should perform this task efficiently.

Input

Your input is a non-empty list L of integers in the range 0 – 99999 inclusive. It is given in the native format of your language, or simply delimited by spaces.

Output

Your output is a truthy value if L can be broken into an increasing and a decreasing subsequence, and a falsy value otherwise. The subsequences need not be strictly increasing or decreasing, and either of them may be empty.

Rules and bonuses

You can write a full program or a function. The lowest byte count wins, and standard loopholes are disallowed. Furthermore, brute forcing is forbidden in this challenge: your program must run in polynomial time in the length of the input.

You are not required to actually return the two subsequences, but there is a bonus of -20% for doing so. To make the bonus easier to claim in statically typed languages, it is acceptable to return a pair of empty lists for the falsy instances.

Test cases

Given in the format input -> None for falsy inputs and input -> inc dec for truthy inputs. Only one possible pair of subsequences is given here; there may be more.

[4,9,2,8,3,7,4,6,5] -> None
[0,99999,23423,5252,27658,8671,43245,53900,22339] -> None
[10,20,30,20,32,40,31,40,50] -> None
[49,844,177,974,654,203,65,493,844,767,304,353,415,425,857,207,871,823,768,110,400,710,35,37,88,587,254,680,454,240,316,47,964,953,345,644,582,704,373,36,114,224,45,354,172,671,977,85,127,341,268,506,455,6,677,438,690,309,270,567,11,16,725,38,700,611,194,246,34,677,50,660,135,233,462,777,48,709,799,929,600,297,98,39,750,606,859,46,839,51,601,499,176,610,388,358,790,948,583,39] -> None
[0,1,2,3,4] -> [0,1,2,3,4] []
[4,3,2,1,0] -> [] [4,3,2,1,0]
[1,9,2,8,3,7,4,6,5] -> [1,2,3,4,6] [9,8,7,5]
[71414,19876,23423,54252,27658,48671,43245,53900,22339] -> [19876,23423,27658,48671,53900] [71414,54252,43245,22339]
[10,20,30,20,30,40,30,40,50] -> [10,20,20,30,40,40,50] [30,30]
[0,3,7,13,65,87,112,43,22,1] -> [0,3,7,13,65,87,112] [43,22,1]
[7,4,4,7,4,7,7,4,7,4,4,4,7,7] -> [7,7,7,7,7,7,7] [4,4,4,4,4,4,4]
[7,997,991,957,956,952,7,8,21,924,21,923,22,38,42,44,920,49,58,67,71,83,84,85,917,89,907,896,878,878,90,861,115,860,125,128,140,148,858,155,160,836,164,182,826,191,824,805,195,792,205,782,206,210,769,213,756,748,214,745,724,701,234,241,693,268,685,293,679,297,334,671,336,669,341,652,356,648,362,364,370,375,386,630,622,388,389,618,398,408,468,615,470,533,611,539,544,609,586,582,572,565,547,602,536,619,624,528,512,631,640,649,669,671,677,505,678,723,743,489,489,473,454,757,446,445,758,759,764,445,431,770,429,426,418,409,790,383,379,366,363,791,358,795,809,827,835,356,353,841,844,333,867,323,317,879,311,881,309,896,282,281,897,263,904,237,236,226,202,195,914,186,177,917,920,157,926,936,154,138,943,131,945,100,98,947,957,964,95,973,989,57,43,32,21,16,13,11,8,0] -> [7,7,8,21,21,22,38,42,44,49,58,67,71,83,84,85,89,90,115,125,128,140,148,155,160,164,182,191,195,205,206,210,213,214,234,241,268,293,297,334,336,341,356,362,364,370,375,386,388,389,398,408,468,470,533,539,544,586,602,619,624,631,640,649,669,671,677,678,723,743,757,758,759,764,770,790,791,795,809,827,835,841,844,867,879,881,896,897,904,914,917,920,926,936,943,945,947,957,964,973,989] [997,991,957,956,952,924,923,920,917,907,896,878,878,861,860,858,836,826,824,805,792,782,769,756,748,745,724,701,693,685,679,671,669,652,648,630,622,618,615,611,609,582,572,565,547,536,528,512,505,489,489,473,454,446,445,445,431,429,426,418,409,383,379,366,363,358,356,353,333,323,317,311,309,282,281,263,237,236,226,202,195,186,177,157,154,138,131,100,98,95,57,43,32,21,16,13,11,8,0] 

Answer 1

Pyth, 34 bytes

.N|!N|&ghNT:tNhNY&gYhN:tNThN:QZ^T5

Test Suite

Uses memoized recursion to keep the runtime down. Defines a 3 input function :, which takes inputs `list suffix, end of increasing sequence, end of decreasing sequence.

Answer 2

Brachylog, 16 bytes - 20% = 12.8 (but it's almost certainly not polynomial)

⊇≥₁X&⊇≤₁Y;X.cp?∧

Try it online!

Fails if there's no pair of compliant subsequences and outputs them through its output variable if there is one (but will just print true. if it's run as a program). I say it's almost certainly not polynomial because the beauty of Brachylog is that since it's a declarative language, you don't do so much in the way of implementing an algorithm as you do just describing relationships between variables and asking the computer to crank out results. So chances are this is hardcore brute force, but I spent long enough copy pasting the test cases (two of which it just times out on) that I feel like I should submit this anyhow, if for no other reason than to drag this challenge up from the back of the decision-problem "Newest" list.

   X                X is a
 ≥₁                 non-increasing
⊇                   sublist of the input
    &               and
        Y           Y is a
      ≤₁            non-decreasing
     ⊇              sublist of the input
         ;X         which paired with X
           .        is the output variable
            c       which when its elements are concatenated
             p      is a permutation of
              ?     the input
               ∧    which is not unified with the output.

Answer 3

Haskell, 65 bytes

(>[]).foldl(%)[(0,9^6)]
p%x=do(u,d)<-p;[(x,d)|x>=u]++[(u,x)|x<=d]

Try it online!

Iterates through the list, tracking the possible pairs (u,d) of the max of the increasing sequence and the min of the decreasing one. Each new element x replaces either u or d, which corresponds to it being append to that subsequence. It could be that both or neither options are valid. In the end, we check that the list of possibilities is nonempty.

The initial bounds (0,9^6) use that the problem specifies the numbers to be in the range 0 – 99999. A more general solution could do (1/0,-1/0) to makes (-inf,inf).