Skip to content

Instantly share code, notes, and snippets.

@daniel-j-h
Last active December 21, 2015 10:09
Show Gist options
  • Save daniel-j-h/6289888 to your computer and use it in GitHub Desktop.
Save daniel-j-h/6289888 to your computer and use it in GitHub Desktop.
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].
/*
* 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, " "));
}
(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]
[]]))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment