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
uint32_t	trappedRainwater (const std::vector< uint32_t > &heights)
	Function to calculate the trapped rainwater.

Detailed Description

Dynamic Programming algorithms.

Dynamic programming algorithms.

Namespace for dynamic programming algorithms.

For std::vector.

for std::vector

Dynamic Programming algorithm.

for IO operations

Dynamic Programming Algorithms.

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

for assert for std::pow

Dynamic Programming algorithms

for assert for std::max for std::uint32_t for io operations

Dynamic Programming algorithms

for assert for std::max for std::uint64_t for IO operations

Dynamic Programming algorithms

for assert for std::string for std::vector

for assert for IO operations

Dynamic Programming algorithms

for assert for std::uint64_t for IO operations

Dynamic Programming algorithms

for std::assert for IO operations for unordered map

Dynamic Programming algorithms

For std::min and std::max For assert For std::size_t

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

Definition at line 39 of file armstrong_number_templated.cpp.

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

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

Definition at line 40 of file longest_increasing_subsequence.cpp.

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

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

Definition at line 31 of file longest_palindromic_subsequence.cpp.

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

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

Definition at line 26 of file maximum_circular_subarray.cpp.

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

trappedRainwater()

uint32_t dynamic_programming::trappedRainwater

(

const std::vector< uint32_t > &

heights

)

Function to calculate the trapped rainwater.

Parameters

heights

Array representing the heights of walls

Returns

The amount of trapped rainwater

Definition at line 27 of file trapped_rainwater.cpp.

                                                              {
    std::size_t n = heights.size();
    if (n <= 2)
        return 0;  // No water can be trapped with less than 3 walls
 
    std::vector<uint32_t> leftMax(n), rightMax(n);
 
    // Calculate the maximum height of wall to the left of each wall
    leftMax[0] = heights[0];
    for (std::size_t i = 1; i < n; ++i) {
        leftMax[i] = std::max(leftMax[i - 1], heights[i]);
    }
 
    // Calculate the maximum height of wall to the right of each wall
    rightMax[n - 1] = heights[n - 1];
    for (std::size_t i = n - 2; i < n; --i) {
        rightMax[i] = std::max(rightMax[i + 1], heights[i]);
    }
 
    // Calculate the trapped rainwater between walls
    uint32_t trappedWater = 0;
    for (std::size_t i = 0; i < n; ++i) {
        trappedWater +=
            std::max(0u, std::min(leftMax[i], rightMax[i]) - heights[i]);
    }
 
    return trappedWater;
}