Tag: Tabulation

Longest Common Subsequence of K-sequences

The longest common subsequence (LCS) problem is the problem of finding the longest subsequence that is present in given two sequences in the same order. i.e. find a longest sequence which can be obtained from the first original sequence by deleting some items, and from the second original sequence by deleting other items.

Find Longest Bitonic Subarray in an array

The longest bitonic subarray problem is to find a subarray of a given sequence in which the subarray’s elements are first sorted in in increasing order, then in decreasing order, and the subarray is as long as possible. Strictly ascending or descending subarrays are also accepted.  

Maximum Product Rod Cutting

Given a rod of length n, find the optimal way to cut rod into smaller rods in order to maximize product of price of each of the smaller rod. Assume each rod of length i has price i.