#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/longest-bitonic-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██████████████████████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/dynamic-programming/longest-increasing-subsequence/longest-bitonic-implementation

Repovive

Longest Bitonic Subsequence - Implementation - Longest Increasing Subsequence | Dynamic Programming | Repovive

Repovive.

Dynamic Programming21 sections · 918 units60h total

Open in Course

Longest Bitonic Subsequence - Implementation

The code

Here's the full solution:

function longestBitonic(nums)
    n := length of nums
    lis := array of size n, all 1
    lds := array of size n, all 1
    // LIS from left
    for i from 1 to n - 1
        for j from 0 to i - 1
            if nums[j] < nums[i]
                lis[i] := max(lis[i], lis[j] + 1)
    // LDS from right (LIS in reverse)
    for i from n - 2 down to 0
        for j from n - 1 down to i + 1
            if nums[j] < nums[i]
                lds[i] := max(lds[i], lds[j] + 1)
    // Combine: bitonic length at i = lis[i] + lds[i] - 1
    maxLen := 0
    for i from 0 to n - 1
        maxLen := max(maxLen, lis[i] + lds[i] - 1)
    return maxLen

Time: $O(n^2)$ . Space: $O(n)$ .

You compute LIS ending at each position, then LDS starting from each position. The bitonic subsequence peaks at position $i$ with length lis[i] + lds[i] - 1. Subtract $1$ because element $i$ is counted in both.