## Problem:

This exercise asks you to develop efficient algorithms to find optimal subsequence of various kinds. A subsequence is anything obtained from a sequence by extracting a subset of ele- ments, but keeping them in the same order; the elements of the subsequence need not be contiguous in the original sequence. For example, the strings C, DAMN, YAIOAI, and DYNAMICPROGRAMMING are all subsequences of the string DYNAMICPROGRAMMING.

Solve all the above problems with efficient dynamic programming with tabulation. You only need to provide:
1. Clear definition of subproblem -- e.g. T[i] defined as longest bitonic subseuqence of A[i:n], etc.
2. Recursion between the subproblems in such a way that can be tabulated; e.g. T[i] = T[i+1] +1
3. One short paragraph describing why the recursion (equality) holds.

## Question 1:
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.

## subproblems:
inc[i] = length of the longest increasing subsequence that ends at i

dec[i] = length of the longest decreasing subsequence that starts at i

## Recurrence:

Base cases: inc[i] = 1 and dec[i] = 1 for all i.

For i = 0..n-1: inc[i] = 1 + max{ inc[j] : 0 ≤ j < i and X[j] < X[i] } (or 1 if set is empty)

For i = n-1..0: dec[i] = 1 + max{ dec[j] : i < j ≤ n-1 and X[j] < X[i] } (or 1 if empty)

so, logest biotonic subsequence is max(inc[i] + dec[i] + 1)

### Time complexity: O(n^2)

## Descritpion:
Every bitonic subsequence has one unique “peak” point where the numbers stop increasing and start decreasing. Everything before this peak forms an increasing subsequence, and everything after it forms a decreasing one. Our algorithm separately finds the best (longest) increasing part and the best decreasing part for each possible peak index. For the actual peak, adding these two lengths together and subtracting one (since the peak itself is counted twice) gives the total length of that bitonic subsequence. Taking the maximum value among all possible peaks gives the overall longest bitonic subsequence.

## Question 2:
Call a sequence X[0:n] of numbers oscillating if X[i]<X[i+1] for all even i, and X[i]> X [i + 1] for all odd i. Describe an efficient algorithm to compute the length of the longest oscillating subsquence of an arbitrary array X of integers.

## subproblems:
U[i] = length of the longest oscillating (start-up) subsequence that ends at i and whose last step is an “up” (something < something).

D[i] = length of the longest oscillating (start-up) subsequence that ends at i and whose last step is a “down” (something > something).

U[i] = 1 → each element alone counts as a sequence.

D[i] = 0 → a sequence can’t end with a “down” step unless it’s already gone “up” first.

## Recurrence:

For each element i:
Look at all previous elements j < i:
If X[j] < X[i] (the value goes up):
You can start a new “up” sequence: U[i] = max(U[i], 2)
Or continue a sequence that last went down: U[i] = max(U[i], D[j] + 1)
If X[j] > X[i] (the value goes down):
You can only continue a sequence that already had an “up”: D[i] = max(D[i], U[j] + 1)

so, it will be answer = max(answer, max(U[i], D[i]));

### Time complexity = O(n^2)

## Description:
Every valid oscillating subsequence that ends at position i must finish with either an “up” or a “down” step. If it ends with an “up,” the previous step must have been “down,” and we use D[j] to track that best sequence. If it ends with a “down,” the previous step must have been “up,” which we track in U[j]. To make sure the sequence starts with an “up,” we only allow a “down” step if there was already at least one “up” before it (that’s why we check U[j] > 1). The rule U[i] = max(U[i], 2) lets us start new sequences with an “up.” By doing this for every element, our tables store the best possible lengths of valid start-up oscillating sequences, and taking the largest value among them gives the final answer.