lissum.cpp

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

template <class ForwardIterator, class Comp = std::less<>>
auto maxSum(ForwardIterator begin,
            ForwardIterator end,
            Comp comp = Comp()) {
    using value_type = typename std::decay<decltype(*begin)>::type;
    
    auto length = std::distance(begin, end);
    auto sumVec = std::vector<value_type>{begin, end};
    
    for(auto firstBegin{begin}; firstBegin != end; ++firstBegin) {
        auto fromBeginToFirstBegin = std::distance(begin, firstBegin);
        
        for(auto secondBegin{begin}; secondBegin != firstBegin; ++secondBegin) {
            auto fromBeginToSecondBegin = std::distance(begin, secondBegin);
            auto newSum = sumVec[fromBeginToSecondBegin] + *firstBegin;
            
            if( comp(*secondBegin, *firstBegin) &&
                comp(sumVec[fromBeginToFirstBegin], newSum)) {
                        sumVec[fromBeginToFirstBegin] = newSum;
            }
        }
    }
    
    return *std::max_element(std::begin(sumVec), std::end(sumVec));
}