Problem

Given an array of positive integers, find the length of the longest bitonic subsequence.

A bitonic subsequence is a sequence that first increases to a peak and then decreases.

Examples

Example 1

1
2
3

Input: nums = [1, 11, 2, 10, 4, 5, 2, 1]
Output: 6
Explanation: The longest bitonic subsequence is [1, 2, 10, 4, 2, 1].

Example 2

1
2
3

Input: nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]
Output: 7
Explanation: The longest bitonic subsequence is [0, 8, 12, 14, 13, 11, 7].

Solution

Method 1 - Dynamic Programming

Intuition

A bitonic subsequence is one that first increases and then decreases. To find the longest bitonic subsequence, we can combine the longest increasing subsequence (LIS) ending at each index with the longest decreasing subsequence (LDS) starting from that index. The peak of the bitonic sequence is where these two meet, and the answer is the maximum sum of LIS and LDS at any index, minus one to avoid double-counting the peak.

For e.g., the longest bitonic subsequence (LBS) in the array nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15], can be shown as shown below:

1
2
3
4
5
6
7

LIS   peak   LDS
 |     |     |
 |     v     |
 |    14     |
 v  12  13   v
 8      11
 0         7

Approach

  1. For each index, compute the length of the longest increasing subsequence (LIS) ending at that index.
  2. For each index, compute the length of the longest decreasing subsequence (LDS) starting from that index.
  3. For every index, calculate LIS[i] + LDS[i] - 1 to get the length of the bitonic subsequence with peak at i.
  4. Return the maximum value among all indices as the answer.

We can easily solve this problem using Longest Increasing Subsequence, so lets focus on it first.

Dry Run

Let LIS(i) represent the length of the longest increasing subsequence ending at index i in the array nums.

For instance, for nums = [0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15]:

1
2
3
4
5
6
7
8
9

LIS(0) = 1  [0]  // a single element forms an increasing subsequence
LIS(1) = 2  [0, 8]
LIS(2) = 2  [0, 4]
LIS(3) = 3  [0, 8, 12] or [0, 4, 12]
LIS(4) = 2  [0, 2]
LIS(5) = 3  [0, 8, 10] or [0, 4, 10] or [0, 2, 10]
LIS(6) = 3  [0, 4, 6] or [0, 2, 6]
LIS(7) = 4  [0, 8, 12, 14] or [0, 4, 12, 14] or [0, 8, 10, 14] or [0, 4, 10, 14] or [0, 4, 6, 14] or [0, 2, 6, 14]
...

For example, LIS(7) is formed by adding nums[7] to the LIS of indices 3, 5, and 6. In general, LIS(i) is built by extending nums[i] to the longest LIS(j) for all j < i where nums[j] < nums[i]. This leads to the recurrence:

1

LIS(i) = max{1 + LIS(j)} for all j < i and nums[j] < nums[i]

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int longestBitonicSubsequence(vector<int>& nums) {
        int n = nums.size();
        vector<int> lis(n, 1), lds(n, 1);
        for (int i = 1; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (nums[i] > nums[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
        for (int i = n - 2; i >= 0; --i)
            for (int j = n - 1; j > i; --j)
                if (nums[i] > nums[j] && lds[i] < lds[j] + 1)
                    lds[i] = lds[j] + 1;
        int ans = 0;
        for (int i = 0; i < n; ++i)
            ans = max(ans, lis[i] + lds[i] - 1);
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func longestBitonicSubsequence(nums []int) int {
    n := len(nums)
    lis := make([]int, n)
    lds := make([]int, n)
    for i := range lis {
        lis[i], lds[i] = 1, 1
    }
    for i := 1; i < n; i++ {
        for j := 0; j < i; j++ {
            if nums[i] > nums[j] && lis[i] < lis[j]+1 {
                lis[i] = lis[j] + 1
            }
        }
    }
    for i := n-2; i >= 0; i-- {
        for j := n-1; j > i; j-- {
            if nums[i] > nums[j] && lds[i] < lds[j]+1 {
                lds[i] = lds[j] + 1
            }
        }
    }
    ans := 0
    for i := 0; i < n; i++ {
        if lis[i]+lds[i]-1 > ans {
            ans = lis[i]+lds[i]-1
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int longestBitonicSubsequence(int[] nums) {
        int n = nums.length;
        int[] lis = new int[n], lds = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(lds, 1);
        for (int i = 1; i < n; i++)
            for (int j = 0; j < i; j++)
                if (nums[i] > nums[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1;
        for (int i = n - 2; i >= 0; i--)
            for (int j = n - 1; j > i; j--)
                if (nums[i] > nums[j] && lds[i] < lds[j] + 1)
                    lds[i] = lds[j] + 1;
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans = Math.max(ans, lis[i] + lds[i] - 1);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    fun longestBitonicSubsequence(nums: IntArray): Int {
        val n = nums.size
        val lis = IntArray(n) { 1 }
        val lds = IntArray(n) { 1 }
        for (i in 1 until n)
            for (j in 0 until i)
                if (nums[i] > nums[j] && lis[i] < lis[j] + 1)
                    lis[i] = lis[j] + 1
        for (i in n - 2 downTo 0)
            for (j in n - 1 downTo i + 1)
                if (nums[i] > nums[j] && lds[i] < lds[j] + 1)
                    lds[i] = lds[j] + 1
        var ans = 0
        for (i in 0 until n)
            ans = maxOf(ans, lis[i] + lds[i] - 1)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

def longest_bitonic_subsequence(nums: list[int]) -> int:
    n = len(nums)
    lis = [1] * n
    lds = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1
    for i in range(n - 2, -1, -1):
        for j in range(n - 1, i, -1):
            if nums[i] > nums[j] and lds[i] < lds[j] + 1:
                lds[i] = lds[j] + 1
    ans = 0
    for i in range(n):
        ans = max(ans, lis[i] + lds[i] - 1)
    return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn longest_bitonic_subsequence(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut lis = vec![1; n];
        let mut lds = vec![1; n];
        for i in 1..n {
            for j in 0..i {
                if nums[i] > nums[j] && lis[i] < lis[j] + 1 {
                    lis[i] = lis[j] + 1;
                }
            }
        }
        for i in (0..n-1).rev() {
            for j in (i+1..n).rev() {
                if nums[i] > nums[j] && lds[i] < lds[j] + 1 {
                    lds[i] = lds[j] + 1;
                }
            }
        }
        let mut ans = 0;
        for i in 0..n {
            ans = ans.max(lis[i] + lds[i] - 1);
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

class Solution {
    longestBitonicSubsequence(nums: number[]): number {
        const n = nums.length;
        const lis = Array(n).fill(1);
        const lds = Array(n).fill(1);
        for (let i = 1; i < n; i++) {
            for (let j = 0; j < i; j++) {
                if (nums[i] > nums[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }
        for (let i = n - 2; i >= 0; i--) {
            for (let j = n - 1; j > i; j--) {
                if (nums[i] > nums[j] && lds[i] < lds[j] + 1) {
                    lds[i] = lds[j] + 1;
                }
            }
        }
        let ans = 0;
        for (let i = 0; i < n; i++) {
            ans = Math.max(ans, lis[i] + lds[i] - 1);
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n^2), reasoning: For each element, we check all previous (for LIS) and all next (for LDS) elements, resulting in nested loops.
  • 🧺 Space complexity: O(n), reasoning: We use two arrays (LIS and LDS) of size n to store intermediate results.