dynamic_programming Namespace Reference

Dynamic Programming algorithms. More...

Functions
uint64_t	LIS (const std::vector< uint64_t > &a, const uint32_t &n)
	Calculate the longest increasing subsequence for the specified numbers. More...

Detailed Description

Dynamic Programming algorithms.

Dynamic programming algorithms.

for std::vector

Dynamic Programming algorithm.

Dynamic Programming Algorithms.

for assert for IO operations for std::string library for std::vector STL library

for assert for std::max for io operations

Dynamic Programming algorithms

for assert for std::max for IO operations

Dynamic Programming algorithms

for assert for IO operations

Dynamic Programming algorithms

Function Documentation

LIS()

uint64_t dynamic_programming::LIS	(	const std::vector< uint64_t > &	a,
		const uint32_t &	n
	)

Calculate the longest increasing subsequence for the specified numbers.

Parameters

a	the array used to calculate the longest increasing subsequence
n	the size used for the arrays

Returns

the length of the longest increasing subsequence in the a array of size n

                                                              {
    std::vector<int> lis(n);
    for (int i = 0; i < n; ++i) {
        lis[i] = 1;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (a[i] > a[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
    int res = 0;
    for (int i = 0; i < n; ++i) {
        res = std::max(res, lis[i]);
    }
    return res;
}

Here is the call graph for this function: