# Longest Bitonic Sequence
### Call a sequence X[0:n] of numbers bitonic if there is an index i with 0<i<n, such that the prefix X[0:i] is increasing and the suffix X[i:n] is decreasing. Describe an efficient algorithm to compute the length of the longest bitonic subsequence of an arbitrary array X of integers.

#### Algorithm Pseudocode

fun longest_bitonic_sequence (A)
{
    var n = len(a);
    var lis = [];
    var lds = [];
    
    // base case: sequence is size <= 1
    if (n <= 1) {
        return n;
    }
    
    // initializes arrays to size n and filled with ones
    for (int i = 0; i < n; i++) {
        lis[i] = 1;
        lds[i] = 1;
    }
    
    // fill up lis array
    for (var i = 1; i < n; i++) {
        for (var j = 0; j < i; j++) {
            if (A[i] > A[j] AND lis[i] < lis[j] + 1)    lis[i] = lis[j] + 1;
        }
    }
    
    // fill up lds array
    for (var i = n-2; i > 0; i++){
        for (var j = n-1; j > i; j++) {
            if (A[i] > A[j] AND lds[i] < lds[j] + 1)    lds[i] = lds[j] + 1;
        }
    }
    
    // compute max subsequence length
    var maxLength = 0;
    var currentLength;
    for (var i = 0; i < n; i++) {
         currentLength = lis[i] + lds[i] - 1;
        if (maxLenght < currentLength)    maxLenght = currentLength;
    }
    
    return maxLength;
}

#### 1. Clear definition of subproblem -- e.g. T[i] defined as longest bitonic subseuqence of A[i:n], etc.
The algorithm will use two DP arrays, LIS[i] and LDS[i], for the input array X[0...n-1]:
* $LIS[i]$: The length of the Longest Increasing Subsequence of $X[0...n-1]$ that ends at index $i$. ($X[i]$ is the last and largest element of the sequence).
* $LDS[i]$: The length of the Longest Decreasing Subsequence of $X[0...n-1]$ that starts at index $i$. ($X[i]$ is the first and largest element of the sequence).

#### 2. Recursion between the subproblems in such a way that can be tabulated; e.g. T[i] = T[i+1] +1
The tables are computed as follows (using an sequence size 1 or less as the base case [returns n]):
* $LIS[i] = 1 + max(\{LIS[j] \mid 0 \le j < i \text{ and } X[j] < X[i]\})$
* This is computed by iterating $i$ from $0$ to $n-1$.
* $LDS[i] = 1 + max(\{LDS[j] \mid i < j < n \text{ and } X[j] < X[i]\})$
* This is computed by iterating $i$ from $n-1$ down to $0$.
* The final answer is the maximum value of $LIS[i] + LDS[i] - 1$ for all $0 \le i < n$. It is -1 as the "peak" is counted in both the increasing and decreasing ssequences.

#### 3. One short paragraph describing why the recursion (equality) holds.
Any bitonic subsequence must have a single "peak" element $X[i]$, which is the largest element in that subsequence. The $LIS[i]$ recurrence calculates the length of the increasing "left side" of the bitonic subsequence that ends at $X[i]$. It does this by finding the longest increasing subsequence ending at some $j$ before $i$ (where $X[j] < X[i]$) and adding 1 (for $X[i]$). The $LDS[i]$ recurrence similarly calculates the length of the decreasing "right side" that starts at $X[i]$ by looking forward to elements $X[j]$ (where $j > i$ and $X[j] < X[i]$). The total length of the longest bitonic subsequence with $X[i]$ as its peak is $LIS[i] + LDS[i] - 1$. We subtract 1 because the peak $X[i]$ is counted in both the $LIS$ and $LDS$ computations. The algorithm finds this value for every possible peak $i$ and takes the maximum.