Find the longest increasing subsequence in N^2 time using dynamic programming.

longest_subsequence.cpp

template<typename Container>
class LongestSubsequence
{
public:
	
	using size_t = unsigned int;
	
	using cache_t = std::unordered_map<size_t, size_t>;
	
	LongestSubsequence(const Container& container)
	: _container(container)
	, _size(static_cast<size_t>(_container.size()))
	{ }
	
	size_t operator()()
	{
		cache_t cache;
		
		return _find(0, std::numeric_limits<long>::min(), cache);
	}
	
private:
	
	template<typename T>
	size_t _find(size_t start, const T& previous, cache_t& cache)
	{
		if (start >= _size) return 0;
		
		if (! cache.count(start))
		{
			size_t longest = 0;
			
			auto distance = _size - start;
			
			for (auto i = start; i < _size; ++i)
			{
				if (_container[i] > previous)
				{
					auto result = _find(i + 1, _container[i], cache) + 1;
					
					if (result > longest) longest = result;
				}
				
				if (--distance < longest) break;
			}
			
			cache[start] = longest;
		}
		
		return cache[start];
	}
	
	const Container& _container;
	
	const size_t _size;
};

template<typename Container>
std::size_t longest_subsequence(Container container)
{
	LongestSubsequence<Container> subsequence(container);
	
	return subsequence();
}