Given a collection of numbers, find the longest monotonic prefix (ascending or descending), i.e. l-m-prefix [3 2 1 2 3 4] => [3 2 1].

c++11-longest-monotonic-prefix.cpp

/*
 * Given a collection of numbers, find the longest monotonic prefix (ascending or descending);
 * e.g.: l-m-prefix [3 2 1 2 3 4] => [3 2 1]
 */

#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iterator>
#include <utility>


/* Returns a range containing the longest monotonic prefix in the range [first, last) */
template<typename ForwardIt>
std::pair<ForwardIt, ForwardIt> longest_monotonic_prefix(ForwardIt first, ForwardIt last) {
  // empty, one or two element range is already longest monotonic prefix
  if (std::distance(first, last) <= 2)
    return { first, last };

  const auto asc_end = std::adjacent_find(first, last, std::greater<typename ForwardIt::value_type>());
  const auto dsc_end = std::adjacent_find(first, last, std::less<typename ForwardIt::value_type>());

  // prefix is full range
  if (asc_end == last || dsc_end == last)
    return { first, last };

  const auto n = 1U + std::max(std::distance(first, asc_end), std::distance(first, dsc_end));

  return { first, std::next(first, n) };
}


int main() {
  std::vector<int> v {3, 2, 1, 2, 3, 4};

  const auto prefix = longest_monotonic_prefix(std::begin(v), std::end(v));

  std::copy(prefix.first, prefix.second, std::ostream_iterator<int>(std::cout, " "));
}

clojure-longest-monotonic-prefix.clj

(defn longest-monotonic-prefix [coll]
  (let [order    (fn [pred coll] (map pred (rest coll) coll))
        asc      (order >= coll)
        dsc      (order <= coll)
        mono     (fn [coll] (count (take-while true? coll)))
        asc-len  (mono asc)
        dsc-len  (mono dsc)]
    (take (inc (max asc-len dsc-len)) coll)))


(dorun (map (comp println longest-monotonic-prefix)
  [[3 2 1 2 3 4],
   [4 3 2 9 2 2],
   [1 2 3 0 1 2]
   [1 1 1]
   []]))