Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving

Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving

Given a sequence as as array of positive integers. Find the length of longest bitonic subsequence. A bitonic subsequence is a subsequence that is first increasing up to a peak value and then decreasing from the peak value. For example, A=[1, 11, 2, 10, 4, 5, 2, 1] the longest bitonic sequence is 1, 2, 4, 5, 2, 1 of length 6. For A=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15] longest bitonic sequence is 0, 8, 12, 14, 13, 11, 7 of length 7. Note that a bitoic sequence starting from a value reaches a peak value in a strict increasing order of values. Then it start decreasing monotonically. So, we can easily perceive that a bitonic sequence consists of a increasing subsequence and a decreasing subsequence. So, a longest bitonic subsequence would be subsequence that consists of a longest increasing subsequence (LIS) ending at peak and a longest decreasing subsequence (LDS) starting at peak. For example longest bitonic subsequence of A=[0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3,

Read full article from Longest Bitonic Sequence - Algorithms and Problem SolvingAlgorithms and Problem Solving