Solving the max-subarray problem from CLRS in C++
I'd really like to use the modern additions to C++ effectively, so please
  let me know where things can be improved.


C++ is suprisingly strong in expressing algorithms in terms of minimal type
requirements quite "easily" with templates. To effectively use the standard
library and its modern additions one should know that

C++ algorithms are written in terms of iterators (or ranges)

So I would like to C++-ify your implementation of max_subarray and show the
usage of some new and cool features of C++17.

Your current version only works for std::vector and with little adaption to
any array-like container. But what if you want to search a std::list or some
container like std::unordered_map (with some projection onto keys or values)?

With that abstraction I wouldn't call the algorithm max_subarray but
max_subrange. The fundamental algorithm is max_crossing_subrange and that
is why I will show you how to C++ify this function


  One of my concerns was using std::numeric_limits::infinity in the code.
  Would this be used in production code? How would one handle something like
  infinity otherwise? 


You are right to question that, because it is not okay or generic in any way.
What if you don't sum numbers but you are folding some lists instead in your
accumulation of neighboured elements?
What you do there is a simple search for a maximum and you could simply
evaluate the first expression instead. Look as an example at std::max_element, to see it is done there.

Just to answer your last concern


  Another concern was using tuples to return multiple values from a function.
  I find that I then have to use std::get quite a lot to access the individual
  elements of the tuple. Is this acceptable?


Yes, that is okay and should be optimized away completely.

Now lets start step-by-step with a generic mas_crossing_subrange algorithm.

Warning: This does not lead to the optimal algorithm (which is O(N)) but just shows how to express algorithms in a C++-way for your example.

Your max_crossing_subarray uses two loops which are essentially same but reversed in their direction. In fact you can express it as one function using std::reverse_iterator. Lets refactor a sub function which performs the loop. An Iterator version would look like this:

/// \brief Fixing the first position we search an end position which
///        maximises the sum from first to end.
template &lt;
    typename I,
    typename T = value_type_t&lt;I&gt;
&gt;
constexpr std::pair&lt;I, T&gt;
max_sum_not_empty(I first, I last, const T&amp; init = T{})
noexcept
{
    assert(first != last);
    auto max = std::make_pair(first, *first);
    auto current_sum = max.second;
    for (auto iter{std::next(first)}; iter != last; ++iter) {
        current_sum = current_sum + *iter;
        if (max &lt; current_sum) {
            max = std::make_pair(iter, current_sum);
        }
    }
    return max;
}


But this isn't totally generic either. What if we want to generalise the accumulation to not just sums but any given fold operator f: X x X -&gt; X (we can not use f: Y x X -&gt; Y in max_crossing) where summation and less-comparison are default behaviour. It would look like this:

template &lt;
    typename I,
    typename T = value_type_t&lt;I&gt;,
    typename F = std::plus&lt;&gt;,
    typename P = std::less&lt;&gt;
&gt;
constexpr std::pair&lt;I, T&gt; max_accumulation_not_empty(
        I first, I last, const T&amp; init = T{}, F op = F{}, P pred = P{})
noexcept (
    std::is_nothrow_callable_v&lt;F(const T&amp;, reference_t&lt;I&gt;)&gt; &amp;&amp;
    std::is_nothrow_callable_v&lt;P(const T&amp;, const T&amp;)&gt;
)
{
    assert(first != last);
    auto max = std::make_pair(first, std::invoke(op, init, *first));
    auto current_sum = max.second;
    for (auto iter{std::next(first)}; iter != last; ++iter) {
        current_sum = std::invoke(op, current_sum, *iter);
        if (std::invoke(pred, max.second, current_sum)) {
            max = std::make_pair(iter, current_sum);
        }
    }
    return max;
}


The reversed algorithm can be written as

template &lt;
    typename I,
    typename T = value_type_t&lt;I&gt;,
    typename F = std::plus&lt;&gt;,
    typename P = std::less&lt;&gt;
&gt;
constexpr std::pair&lt;I, T&gt; reverse_max_accumulation_not_empty(
        I first, I last, const T&amp; init = T{}, F op = F{}, P pred = P{})
noexcept (
    std::is_nothrow_callable_v&lt;F(const T&amp;, reference_t&lt;I&gt;)&gt; &amp;&amp;
    std::is_nothrow_callable_v&lt;P(const T&amp;, const T&amp;)&gt;
)
{
    auto rfirst = std::make_reverse_iterator(last);
    auto rlast = std::make_reverse_iterator(first);
    auto [rbest, sum] = max_accumulation_not_empty(rfirst, rlast, init,
                std::ref(op), std::ref(pred));
    auto best = std::next(rbest).base();
    return std::make_pair(best, sum);
}


Your max_crossing algorithm can be then given as

template &lt;
    typename I,
    typename T = value_type_t&lt;I&gt;,
    typename F = std::plus&lt;&gt;,
    typename P = std::less&lt;&gt;
&gt;
constexpr std::tuple&lt;I, difference_type_t&lt;I&gt;, T&gt;
max_crossing_subrange(I first, I mid, I last, const T&amp; init = T{},
        F op = F{}, P pred = P{})
noexcept (
    std::is_nothrow_callable_v&lt;F(const T&amp;, reference_t&lt;I&gt;)&gt; &amp;&amp;
    std::is_nothrow_callable_v&lt;P(const T&amp;, const T&amp;)&gt;
)
{
    assert(first != mid &amp;&amp; mid != last);
    auto [best_left, left_sum] = reverse_max_accumulation_not_empty(
            first, mid, init, std::ref(op), std::ref(pred));
    auto [best_right, right_sum] = max_accumulation_not_empty(
            mid, last, init, std::ref(op), std::ref(pred));
    auto length = std::distance(best_left, best_right);
    // here comes a strong assumption: op(left_sum, right_sum) needs
    // an operator op: X x X -&gt; X
    return {best_left, length, op(left_sum, right_sum)};
}


If this would lead to an optimal algorithm it would look like this in production code. As an exercise: Try to finish this and proof that the assertions always evaluates to true.