One goes up, the other comes down
Pyth, 34 bytes

.N|!N|&amp;ghNT:tNhNY&amp;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.