Example: Longest Increasing Bitonic Sequence

You have to find the longest bitonic sequence (longest sequence of numbers that first only increases then only decreases).

2 -1 4 3 5 -1 3 2

• We use two arrays,

  • one where we track the longest increasing sequence from left to right
  • one were we track the longest decreasing from right to left

• Increasing 1 1 2 2 3 1 2 2

• Decreasing 2 1 3 2 3 1 2 1

The longest is max (I[i] + D[i] - 1) =>5: 2, 3, 5, 3, 2

maxBitonic(x)
    n = x.len
    inc[0] = 1
    // max increasing
    for j = 1 to n - 1
        for i = 0 to j - 1
            c[i] = 1
            if x[j] > x[i]
                c[j] = max(c[j], c[i] + 1)

    // decreasing
    for j = n - 2 to 0
        for i = n - 1 to j + 1
            d[i] = 1
            if x[j] > x[i]
                c[j] = max(c[j], c[i] + 1)

    maxL = 0
    for i = 0 to n-1
        maxL = max(maxL, c[i] + c[i] - 1)

    return maxL