dynamic_programming Namespace Reference

Dynamic Programming algorithms. More...

Functions
template<typename T >
bool	is_armstrong (const T &number)
	Checks if the given number is armstrong or not.
uint64_t	LIS (const std::vector< uint64_t > &a, const uint32_t &n)
	Calculate the longest increasing subsequence for the specified numbers.
std::string	lps (const std::string &a)
	Function that returns the longest palindromic subsequence of a string.
int	maxCircularSum (std::vector< int > &arr)
	returns the maximum contiguous circular sum of an array

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

for std::assert for IO operations for unordered map

Dynamic Programming algorithms

Function Documentation

is_armstrong()

template<typename T >

bool dynamic_programming::is_armstrong

(

const T &

number

)

Checks if the given number is armstrong or not.

Parameters

number

the number to check

Returns

false if the given number is NOT armstrong

true if the given number IS armstrong

                                   {
    int count = 0, temp = number, result = 0, rem = 0;
 
    // Count the number of digits of the given number.
    // For example: 153 would be 3 digits.
    while (temp != 0) {
        temp /= 10;
        count++;
    }
 
    // Calculation for checking of armstrongs number i.e.
    // in an n-digit number sum of the digits is raised to a power of `n` is
    // equal to the original number.
    temp = number;
    while (temp != 0) {
        rem = temp % 10;
        result += static_cast<T>(std::pow(rem, count));
        temp /= 10;
    }
 
    if (result == number) {
        return true;
    } else {
        return false;
    }
}

Here is the call graph for this function:

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:

lps()

std::string dynamic_programming::lps

(

const std::string &

a

)

Function that returns the longest palindromic subsequence of a string.

Parameters

a	string whose longest palindromic subsequence is to be found

Returns

longest palindromic subsequence of the string

                                  {
    const auto b = std::string(a.rbegin(), a.rend());
    const auto m = a.length();
    using ind_type = std::string::size_type;
    std::vector<std::vector<ind_type> > res(m + 1,
                                            std::vector<ind_type>(m + 1));
 
    // Finding the length of the longest
    // palindromic subsequence and storing
    // in a 2D array in bottoms-up manner
    for (ind_type i = 0; i <= m; i++) {
        for (ind_type j = 0; j <= m; j++) {
            if (i == 0 || j == 0) {
                res[i][j] = 0;
            } else if (a[i - 1] == b[j - 1]) {
                res[i][j] = res[i - 1][j - 1] + 1;
            } else {
                res[i][j] = std::max(res[i - 1][j], res[i][j - 1]);
            }
        }
    }
    // Length of longest palindromic subsequence
    auto idx = res[m][m];
    // Creating string of index+1 length
    std::string ans(idx, '\0');
    ind_type i = m, j = m;
 
    // starting from right-most bottom-most corner
    // and storing them one by one in ans
    while (i > 0 && j > 0) {
        // if current characters in a and b are same
        // then it is a part of the ans
        if (a[i - 1] == b[j - 1]) {
            ans[idx - 1] = a[i - 1];
            i--;
            j--;
            idx--;
        }
        // If they are not same, find the larger of the
        // two and move in that direction
        else if (res[i - 1][j] > res[i][j - 1]) {
            i--;
        } else {
            j--;
        }
    }
 
    return ans;
}

Here is the call graph for this function:

maxCircularSum()

int dynamic_programming::maxCircularSum

(

std::vector< int > &

arr

)

returns the maximum contiguous circular sum of an array

Parameters

arr	is the array/vector

Returns

int which is the maximum sum

{
    // Edge Case
    if (arr.size() == 1)
        return arr[0];
  
    // Sum variable which stores total sum of the array.
    int sum = 0;
    for (int i = 0; i < arr.size(); i++) {
        sum += arr[i];
    }
  
    // Every variable stores first value of the array.
    int current_max = arr[0], max_so_far = arr[0], current_min = arr[0], min_so_far = arr[0];
  
    // Concept of Kadane's Algorithm
    for (int i = 1; i < arr.size(); i++) {
        // Kadane's Algorithm to find Maximum subarray sum.
        current_max = std::max(current_max + arr[i], arr[i]);
        max_so_far = std::max(max_so_far, current_max);
  
        // Kadane's Algorithm to find Minimum subarray sum.
        current_min = std::min(current_min + arr[i], arr[i]);
        min_so_far = std::min(min_so_far, current_min);
    }
  
    if (min_so_far == sum)
        return max_so_far;
  
    // Return the maximum value
    return std::max(max_so_far, sum - min_so_far);
}

Here is the call graph for this function: