longest_increasing_subsequence.cpp File Reference

Calculate the length of the longest increasing subsequence in an array. More...

#include <cassert>
#include <climits>
#include <iostream>
#include <vector>

Include dependency graph for longest_increasing_subsequence.cpp:

Namespaces
namespace	dynamic_programming
	Dynamic Programming algorithms.

Functions
uint64_t	dynamic_programming::LIS (const std::vector< uint64_t > &a, const uint32_t &n)
	Calculate the longest increasing subsequence for the specified numbers.
static void	test ()
	Self-test implementations.
int	main (int argc, char const *argv[])
	Main function.

Detailed Description

Calculate the length of the longest increasing subsequence in an array.

In computer science, the longest increasing subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order, lowest to highest, and in which the subsequence is as long as possible. This subsequence is not necessarily contiguous, or unique. Longest increasing subsequences are studied in the context of various disciplines related to mathematics, including algorithmics, random matrix theory, representation theory, and physics. The longest increasing subsequence problem is solvable in time O(n log n), where n denotes the length of the input sequence.

Author

Krishna Vedala

David Leal

Function Documentation

main()

int main	(	int	argc,
		char const *	argv[] )

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

                                       {
    uint32_t n = 0;
 
    std::cout << "Enter size of array: ";
    std::cin >> n;
 
    std::vector<uint64_t> a(n);
 
    std::cout << "Enter array elements: ";
    for (int i = 0; i < n; ++i) {
        std::cin >> a[i];
    }
 
    std::cout << "\nThe result is: " << dynamic_programming::LIS(a, n)
              << std::endl;
    test();  // run self-test implementations
 
    return 0;
}

Here is the call graph for this function:

test()

static void test ( )

static

Self-test implementations.

Returns

void

< The longest increasing subsequence is {2,3,4,5,8}

                   {
    std::vector<uint64_t> a = {15, 21, 2, 3, 4, 5, 8, 4, 1, 1};
    uint32_t n = a.size();
 
    uint32_t result = dynamic_programming::LIS(a, n);
    assert(result ==
           5);  ///< The longest increasing subsequence is `{2,3,4,5,8}`
 
    std::cout << "Self-test implementations passed!" << std::endl;
}

Here is the call graph for this function: