longest_increasing_subsequence.cpp File Reference

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

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

Include dependency graph for longest_increasing_subsequence.cpp:

Go to the source code of this file.

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 ()
	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

Definition in file longest_increasing_subsequence.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 79 of file longest_increasing_subsequence.cpp.

           {
    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;
}

test()

void test ( )

static

Self-test implementations.

Returns

void

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

Definition at line 64 of file longest_increasing_subsequence.cpp.

                   {
    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);  
 
    std::cout << "Self-test implementations passed!" << std::endl;
}