Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Bitonic Subsequence

MEDIUMProblemSolveExternal Links

Description

Given an array of positive integers, find the maximum length of a Bitonic subsequence.

A subsequence of an array is called Bitonic if it is first strictly increasing, then strictly decreasing. In other words, a bitonic subsequence rises to a peak element and then falls — both the rising and falling parts must be non-empty.

Important: A purely increasing sequence (no decreasing part) or a purely decreasing sequence (no increasing part) is NOT considered bitonic. Both parts must exist for a valid bitonic subsequence.

Return the maximum length of such a bitonic subsequence. If no valid bitonic subsequence exists, return 0.

Examples

Example 1

Input: nums = [1, 2, 5, 3, 2]

Output: 5

Explanation: The entire array [1, 2, 5, 3, 2] forms a bitonic subsequence. It increases from 1 → 2 → 5 (the peak), then decreases from 5 → 3 → 2. Both the increasing part [1, 2, 5] and decreasing part [5, 3, 2] are non-empty, making this a valid bitonic sequence of length 5.

Example 2

Input: nums = [1, 11, 2, 10, 4, 5, 2, 1]

Output: 6

Explanation: The longest bitonic subsequence is [1, 2, 10, 4, 2, 1] with length 6. It increases from 1 → 2 → 10 (peak at 10), then decreases from 10 → 4 → 2 → 1. Note that we skip elements 11 and 5 to form a longer bitonic sequence.

Example 3

Input: nums = [10, 20, 30]

Output: 0

Explanation: The array is strictly increasing — there is no decreasing part. Since a bitonic subsequence must have both an increasing and a decreasing part, no valid bitonic subsequence exists. Return 0.

Example 4

Input: nums = [10, 10, 10]

Output: 0

Explanation: All elements are identical. There is no strictly increasing or strictly decreasing relationship between any two elements, so no bitonic subsequence can be formed.

Constraints

  • 1 ≤ nums.length ≤ 10³
  • 1 ≤ nums[i] ≤ 10⁴

Editorial

Brute Force

Intuition

A bitonic subsequence has a "mountain" shape — it goes up to a peak, then comes down. The simplest way to find the longest one is to try every possible element as the peak and measure how long the mountain can be around that peak.

For a given peak element at index i:

  • Look to the left of i and find the longest strictly increasing subsequence (LIS) that ends at arr[i]. This gives us the length of the uphill side.
  • Look to the right of i and find the longest strictly decreasing subsequence (LDS) that starts at arr[i]. This gives us the length of the downhill side.
  • The total bitonic length centered at this peak is LIS_left + LDS_right + 1 (the +1 counts the peak itself).

We use recursion for both the LIS and LDS computations. For each element, the recursion makes two choices: include it in the subsequence (if it maintains the ordering) or skip it. Without any caching, we recompute the same subproblems repeatedly, leading to exponential time.

Step-by-Step Explanation

Let's trace with nums = [1, 2, 5, 3, 2]. We try each index as the peak.

Step 1: Try peak at index 2 (value 5). Compute LIS to the left and LDS to the right.

Step 2: LIS ending before peak (looking at indices 0, 1 with values < 5):

  • Call lisEnding(idx=1, prev=5). arr[1]=2, and 2 < 5 → we can include it.
    • Take 2: recurse lisEnding(idx=0, prev=2). arr[0]=1, 1 < 2 → take.
      • Base case (idx < 0): return 0. So this path returns 1.
    • Skip 2: recurse lisEnding(idx=0, prev=5). arr[0]=1, 1 < 5 → take.
      • Returns 1.
    • Result: max(1 + 1, 1) = 2. LIS to the left = 2 (subsequence [1, 2]).

Step 3: LDS starting after peak (looking at indices 3, 4 with values < 5):

  • Call ldsStarting(idx=3, prev=5). arr[3]=3, and 3 < 5 → we can include it.
    • Take 3: recurse ldsStarting(idx=4, prev=3). arr[4]=2, 2 < 3 → take.
      • Returns 1 (base case beyond array). So path returns 1 + 1 = 2.
    • Skip 3: recurse ldsStarting(idx=4, prev=5). arr[4]=2, 2 < 5 → take.
      • Returns 1.
    • Result: max(1 + 1, 1) = 2. LDS to the right = 2 (subsequence [3, 2]).

Step 4: Combine at peak 2: LIS=2, LDS=2, both > 0 → valid bitonic! Length = 2 + 2 + 1 = 5.

Step 5: Try other peaks (0, 1, 3, 4) — none yield a longer valid bitonic.

Result: Maximum bitonic length = 5.

Brute Force — Recursive LIS/LDS Exploration for Peak at Index 2 — Watch how recursion explores all possible increasing subsequences to the left and decreasing subsequences to the right of the peak element 5.

Algorithm

  1. For each index peak from 0 to n-1:
    a. Compute lisLen = longest strictly increasing subsequence ending just before peak where all elements are less than arr[peak] (using recursion scanning leftward)
    b. Compute ldsLen = longest strictly decreasing subsequence starting just after peak where all elements are less than arr[peak] (using recursion scanning rightward)
    c. If both lisLen > 0 and ldsLen > 0, update result = max(result, lisLen + ldsLen + 1)
  2. Return result (or 0 if no valid bitonic found)

Code

class Solution {
public:
    int lisEnding(vector<int>& arr, int idx, int prevVal) {
        if (idx < 0) return 0;
        int skip = lisEnding(arr, idx - 1, prevVal);
        int take = 0;
        if (arr[idx] < prevVal) {
            take = 1 + lisEnding(arr, idx - 1, arr[idx]);
        }
        return max(skip, take);
    }

    int ldsStarting(vector<int>& arr, int idx, int prevVal) {
        if (idx >= (int)arr.size()) return 0;
        int skip = ldsStarting(arr, idx + 1, prevVal);
        int take = 0;
        if (arr[idx] < prevVal) {
            take = 1 + ldsStarting(arr, idx + 1, arr[idx]);
        }
        return max(skip, take);
    }

    int LongestBitonicSequence(int n, vector<int>& arr) {
        if (n < 3) return 0;
        int result = 0;
        for (int peak = 0; peak < n; peak++) {
            int incLen = lisEnding(arr, peak - 1, arr[peak]);
            int decLen = ldsStarting(arr, peak + 1, arr[peak]);
            if (incLen > 0 && decLen > 0) {
                result = max(result, incLen + decLen + 1);
            }
        }
        return result;
    }
};
class Solution:
    def LongestBitonicSequence(self, n, nums):
        if n < 3:
            return 0

        def lis_ending(idx, prev_val):
            if idx < 0:
                return 0
            skip = lis_ending(idx - 1, prev_val)
            take = 0
            if nums[idx] < prev_val:
                take = 1 + lis_ending(idx - 1, nums[idx])
            return max(skip, take)

        def lds_starting(idx, prev_val):
            if idx >= n:
                return 0
            skip = lds_starting(idx + 1, prev_val)
            take = 0
            if nums[idx] < prev_val:
                take = 1 + lds_starting(idx + 1, nums[idx])
            return max(skip, take)

        result = 0
        for peak in range(n):
            inc_len = lis_ending(peak - 1, nums[peak])
            dec_len = lds_starting(peak + 1, nums[peak])
            if inc_len > 0 and dec_len > 0:
                result = max(result, inc_len + dec_len + 1)
        return result
class Solution {
    private int lisEnding(int[] arr, int idx, int prevVal) {
        if (idx < 0) return 0;
        int skip = lisEnding(arr, idx - 1, prevVal);
        int take = 0;
        if (arr[idx] < prevVal) {
            take = 1 + lisEnding(arr, idx - 1, arr[idx]);
        }
        return Math.max(skip, take);
    }

    private int ldsStarting(int[] arr, int idx, int prevVal) {
        if (idx >= arr.length) return 0;
        int skip = ldsStarting(arr, idx + 1, prevVal);
        int take = 0;
        if (arr[idx] < prevVal) {
            take = 1 + ldsStarting(arr, idx + 1, arr[idx]);
        }
        return Math.max(skip, take);
    }

    public int LongestBitonicSequence(int n, int[] arr) {
        if (n < 3) return 0;
        int result = 0;
        for (int peak = 0; peak < n; peak++) {
            int incLen = lisEnding(arr, peak - 1, arr[peak]);
            int decLen = ldsStarting(arr, peak + 1, arr[peak]);
            if (incLen > 0 && decLen > 0) {
                result = Math.max(result, incLen + decLen + 1);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n × 2^n)

For each of the n potential peaks, we compute LIS and LDS using recursion. Each recursive call branches into two choices (include or skip), and the recursion depth is at most n. This gives O(2^n) calls per peak, totaling O(n × 2^n).

The same subproblems (e.g., LIS ending at a particular index with a particular previous value) are recomputed many times across different peak choices, making this extremely wasteful.

Space Complexity: O(n)

The recursion stack goes at most n levels deep (one level per array element). No additional data structures are used.

Why This Approach Is Not Efficient

The brute-force recursion is catastrophically slow because it recomputes the same subproblems exponentially many times. For each peak, the LIS and LDS recursions explore all subsets of the left and right portions of the array.

With n up to 1000, O(n × 2^n) is astronomically large — far beyond any time limit.

The fundamental issue is overlapping subproblems: the longest increasing subsequence ending at index j with a given previous element is the same regardless of which peak we're currently evaluating. Similarly, the LDS computation repeats work across peaks.

Instead of recursively computing LIS/LDS from scratch for each peak, we can precompute them once for every index using dynamic programming. The key insight: LIS[i] (longest increasing subsequence ending at index i) depends only on LIS values at earlier indices, and LDS[i] (longest decreasing subsequence starting at index i) depends only on LDS values at later indices. Both can be computed in O(n²) with simple tabulation.

Better Approach - DP Tabulation (LIS + LDS)

Intuition

Instead of recomputing LIS and LDS for each peak from scratch, we precompute two arrays:

  1. LIS[i] = length of the longest strictly increasing subsequence ending at index i (computed left to right).
  2. LDS[i] = length of the longest strictly decreasing subsequence starting at index i (computed right to left).

Think of LIS[i] as "how high can the mountain rise if it peaks at index i?" and LDS[i] as "how far can the mountain descend after peaking at index i?"

For each index i, if both LIS[i] > 1 (there's at least one element before it that's smaller) and LDS[i] > 1 (there's at least one element after it that's smaller), then a valid bitonic subsequence exists with peak at i. Its length is LIS[i] + LDS[i] - 1 (subtract 1 because the peak element is counted in both arrays).

Both arrays are computed using the classic LIS dynamic programming approach: for each element, check all previous (or subsequent) elements and update if the ordering condition is met.

Step-by-Step Explanation

Let's trace with nums = [1, 2, 5, 3, 2].

Phase 1: Compute LIS (left to right)
Initialize LIS = [1, 1, 1, 1, 1].

Step 1: i=0 (val=1). No elements before it. LIS[0] = 1.

Step 2: i=1 (val=2). Check j=0: arr[0]=1 < 2 → LIS[1] = max(1, LIS[0]+1) = 2.

Step 3: i=2 (val=5). Check j=0: 1 < 5 → candidate 2. j=1: 2 < 5 → LIS[2] = max(2, LIS[1]+1) = 3.

Step 4: i=3 (val=3). Check j=0: 1 < 3 → candidate 2. j=1: 2 < 3 → candidate 3. j=2: 5 > 3, skip. LIS[3] = 3.

Step 5: i=4 (val=2). Check j=0: 1 < 2 → candidate 2. j=1: 2 = 2, not strictly less, skip. LIS[4] = 2.

LIS = [1, 2, 3, 3, 2].

Phase 2: Compute LDS (right to left)
Initialize LDS = [1, 1, 1, 1, 1].

Step 6: i=4 (val=2). No elements after it. LDS[4] = 1.

Step 7: i=3 (val=3). Check j=4: arr[4]=2 < 3 → LDS[3] = max(1, LDS[4]+1) = 2.

Step 8: i=2 (val=5). Check j=3: 3 < 5 → max(1, LDS[3]+1) = 3. j=4: 2 < 5 → max(3, LDS[4]+1) = 3. LDS[2] = 3.

Step 9: i=1 (val=2). Check j=2: 5 > 2, skip. j=3: 3 > 2, skip. j=4: 2 = 2, skip. LDS[1] = 1.

Step 10: i=0 (val=1). All subsequent elements are ≥ 1. LDS[0] = 1.

LDS = [1, 1, 3, 2, 1].

Phase 3: Combine

Step 11: For each i, check if LIS[i] > 1 AND LDS[i] > 1:

  • i=0: LIS=1, LDS=1 → invalid (no increasing part before peak)
  • i=1: LIS=2, LDS=1 → invalid (no decreasing part after peak)
  • i=2: LIS=3, LDS=3 → valid! Length = 3 + 3 - 1 = 5
  • i=3: LIS=3, LDS=2 → valid! Length = 3 + 2 - 1 = 4
  • i=4: LIS=2, LDS=1 → invalid

Result: Maximum = 5.

DP Tabulation — Building LIS and LDS Arrays — Watch how we fill the LIS array left-to-right, then the LDS array right-to-left, and finally combine them to find the longest bitonic subsequence.

Algorithm

  1. If n < 3, return 0 (need at least 3 elements for a bitonic sequence)
  2. Create array LIS of size n, initialized to 1
  3. Compute LIS (left to right): For each i from 1 to n-1:
    • For each j from 0 to i-1:
      • If arr[i] > arr[j]: update LIS[i] = max(LIS[i], LIS[j] + 1)
  4. Create array LDS of size n, initialized to 1
  5. Compute LDS (right to left): For each i from n-2 down to 0:
    • For each j from i+1 to n-1:
      • If arr[i] > arr[j]: update LDS[i] = max(LDS[i], LDS[j] + 1)
  6. Combine: For each i from 0 to n-1:
    • If LIS[i] > 1 AND LDS[i] > 1: update result = max(result, LIS[i] + LDS[i] - 1)
  7. Return result

Code

class Solution {
public:
    int LongestBitonicSequence(int n, vector<int>& arr) {
        if (n < 3) return 0;

        vector<int> lis(n, 1), lds(n, 1);

        // Compute LIS ending at each index (left to right)
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    lis[i] = max(lis[i], lis[j] + 1);
                }
            }
        }

        // Compute LDS starting at each index (right to left)
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    lds[i] = max(lds[i], lds[j] + 1);
                }
            }
        }

        // Combine: find the best peak
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                result = max(result, lis[i] + lds[i] - 1);
            }
        }
        return result;
    }
};
class Solution:
    def LongestBitonicSequence(self, n, nums):
        if n < 3:
            return 0

        lis = [1] * n
        lds = [1] * n

        # Compute LIS ending at each index
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    lis[i] = max(lis[i], lis[j] + 1)

        # Compute LDS starting at each index
        for i in range(n - 2, -1, -1):
            for j in range(i + 1, n):
                if nums[i] > nums[j]:
                    lds[i] = max(lds[i], lds[j] + 1)

        # Combine
        result = 0
        for i in range(n):
            if lis[i] > 1 and lds[i] > 1:
                result = max(result, lis[i] + lds[i] - 1)
        return result
class Solution {
    public int LongestBitonicSequence(int n, int[] arr) {
        if (n < 3) return 0;

        int[] lis = new int[n];
        int[] lds = new int[n];
        Arrays.fill(lis, 1);
        Arrays.fill(lds, 1);

        // Compute LIS ending at each index
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j]) {
                    lis[i] = Math.max(lis[i], lis[j] + 1);
                }
            }
        }

        // Compute LDS starting at each index
        for (int i = n - 2; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (arr[i] > arr[j]) {
                    lds[i] = Math.max(lds[i], lds[j] + 1);
                }
            }
        }

        // Combine
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                result = Math.max(result, lis[i] + lds[i] - 1);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n²)

Computing LIS requires a double loop: the outer loop runs n times, and the inner loop runs up to i times for each i, giving O(n²) total. Computing LDS uses the same structure, also O(n²). The combination step is O(n). Overall: O(n²) + O(n²) + O(n) = O(n²).

With n ≤ 1000: approximately 1,000,000 operations — well within time limits.

Space Complexity: O(n)

We use two arrays of size n (LIS and LDS) plus a few variables. Total auxiliary space is O(n).

Why This Approach Is Not Efficient

The O(n²) tabulation is a huge improvement over exponential brute force, and for n ≤ 1000 it runs comfortably within time limits. However, the quadratic time comes from the nested loop: for each element, we scan all previous elements (for LIS) or all subsequent elements (for LDS) to check the ordering condition.

This is the same bottleneck as the classic LIS problem. The key realization is that we don't need to check all previous elements. Instead, we can maintain a sorted structure (often called "patience sorting" or a "tails" array) that allows us to find the correct position for each element using binary search in O(log n) time.

By replacing the O(n) inner loop with an O(log n) binary search, we reduce the total time from O(n²) to O(n log n). Since both LIS and LDS computations benefit from this optimization, the overall complexity drops to O(n log n).

Optimal Approach - Binary Search Based LIS + LDS

Intuition

The optimal approach leverages a well-known technique for computing the Longest Increasing Subsequence in O(n log n) time, known as patience sorting.

The idea is to maintain a tails array where tails[k] stores the smallest possible last element of any increasing subsequence of length k+1. This array is always sorted, which means we can use binary search to find where each new element fits.

For each element arr[i]:

  • Use binary search to find the first element in tails that is ≥ arr[i] (this is lower_bound).
  • If no such element exists (arr[i] is larger than all tails), append it — we've extended the longest known subsequence.
  • Otherwise, replace that element — we've found a better (smaller) tail for a subsequence of the same length.
  • The position where we placed arr[i] tells us LIS[i] = position + 1.

For LDS, we apply the exact same technique but scan the array from right to left — effectively computing the longest increasing subsequence on the reversed suffix, which is equivalent to the longest decreasing subsequence starting at each index.

Finally, we combine LIS and LDS exactly as before: for each index i with both LIS[i] > 1 and LDS[i] > 1, the bitonic length is LIS[i] + LDS[i] - 1.

Step-by-Step Explanation

Let's trace with nums = [1, 2, 5, 3, 2].

Phase 1: Compute LIS using binary search
tails = [] (empty)

Step 1: arr[0]=1. tails is empty → append 1. tails=[1]. LIS[0] = 1.

Step 2: arr[1]=2. Binary search for first ≥ 2 in [1] → not found (2 > 1). Append. tails=[1, 2]. LIS[1] = 2.

Step 3: arr[2]=5. Search for first ≥ 5 in [1, 2] → not found. Append. tails=[1, 2, 5]. LIS[2] = 3.

Step 4: arr[3]=3. Search for first ≥ 3 in [1, 2, 5] → found at position 2 (element 5). Replace: tails=[1, 2, 3]. LIS[3] = 3.

Step 5: arr[4]=2. Search for first ≥ 2 in [1, 2, 3] → found at position 1 (element 2). Replace: tails=[1, 2, 3]. LIS[4] = 2.

LIS = [1, 2, 3, 3, 2]. ✓

Phase 2: Compute LDS using binary search (right to left)
tails = [] (reset)

Step 6: i=4, arr[4]=2. Append. tails=[2]. LDS[4] = 1.

Step 7: i=3, arr[3]=3. 3 > 2 → append. tails=[2, 3]. LDS[3] = 2.

Step 8: i=2, arr[2]=5. 5 > 3 → append. tails=[2, 3, 5]. LDS[2] = 3.

Step 9: i=1, arr[1]=2. Search for first ≥ 2 in [2, 3, 5] → position 0. Replace: tails=[2, 3, 5]. LDS[1] = 1.

Step 10: i=0, arr[0]=1. Search for first ≥ 1 in [2, 3, 5] → position 0. Replace: tails=[1, 3, 5]. LDS[0] = 1.

LDS = [1, 1, 3, 2, 1]. ✓

Phase 3: Combine — same as before. Best at i=2: 3 + 3 - 1 = 5.

Result: 5.

Binary Search LIS/LDS — Patience Sorting with O(log n) Lookups — Watch how each element finds its position in the sorted tails array using binary search, computing LIS and LDS values in O(n log n) total time.

Algorithm

  1. If n < 3, return 0
  2. Compute LIS using patience sorting:
    • Maintain a sorted tails array
    • For each arr[i] (left to right):
      • Binary search (lower_bound) for first element ≥ arr[i] in tails
      • If not found: append arr[i] to tails
      • If found at position pos: replace tails[pos] = arr[i]
      • Set LIS[i] = pos + 1
  3. Compute LDS using patience sorting (right to left):
    • Reset tails to empty
    • For each arr[i] from index n-1 down to 0:
      • Same binary search and replace/append logic
      • Set LDS[i] = pos + 1
  4. Combine: For each i, if LIS[i] > 1 and LDS[i] > 1, update result
  5. Return result

Code

class Solution {
public:
    int LongestBitonicSequence(int n, vector<int>& arr) {
        if (n < 3) return 0;

        vector<int> lis(n), lds(n);

        // Compute LIS using patience sorting
        vector<int> tails;
        for (int i = 0; i < n; i++) {
            auto it = lower_bound(tails.begin(), tails.end(), arr[i]);
            int pos = it - tails.begin();
            if (it == tails.end()) {
                tails.push_back(arr[i]);
            } else {
                *it = arr[i];
            }
            lis[i] = pos + 1;
        }

        // Compute LDS using patience sorting (right to left)
        tails.clear();
        for (int i = n - 1; i >= 0; i--) {
            auto it = lower_bound(tails.begin(), tails.end(), arr[i]);
            int pos = it - tails.begin();
            if (it == tails.end()) {
                tails.push_back(arr[i]);
            } else {
                *it = arr[i];
            }
            lds[i] = pos + 1;
        }

        // Combine
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                result = max(result, lis[i] + lds[i] - 1);
            }
        }
        return result;
    }
};
from bisect import bisect_left

class Solution:
    def LongestBitonicSequence(self, n, nums):
        if n < 3:
            return 0

        lis = [0] * n
        lds = [0] * n

        # Compute LIS using binary search
        tails = []
        for i in range(n):
            pos = bisect_left(tails, nums[i])
            if pos == len(tails):
                tails.append(nums[i])
            else:
                tails[pos] = nums[i]
            lis[i] = pos + 1

        # Compute LDS using binary search (right to left)
        tails = []
        for i in range(n - 1, -1, -1):
            pos = bisect_left(tails, nums[i])
            if pos == len(tails):
                tails.append(nums[i])
            else:
                tails[pos] = nums[i]
            lds[i] = pos + 1

        # Combine
        result = 0
        for i in range(n):
            if lis[i] > 1 and lds[i] > 1:
                result = max(result, lis[i] + lds[i] - 1)
        return result
class Solution {
    public int LongestBitonicSequence(int n, int[] arr) {
        if (n < 3) return 0;

        int[] lis = new int[n];
        int[] lds = new int[n];

        // Compute LIS using binary search
        List<Integer> tails = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int pos = Collections.binarySearch(tails, arr[i]);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) {
                tails.add(arr[i]);
            } else {
                tails.set(pos, arr[i]);
            }
            lis[i] = pos + 1;
        }

        // Compute LDS using binary search (right to left)
        tails.clear();
        for (int i = n - 1; i >= 0; i--) {
            int pos = Collections.binarySearch(tails, arr[i]);
            if (pos < 0) pos = -(pos + 1);
            if (pos == tails.size()) {
                tails.add(arr[i]);
            } else {
                tails.set(pos, arr[i]);
            }
            lds[i] = pos + 1;
        }

        // Combine
        int result = 0;
        for (int i = 0; i < n; i++) {
            if (lis[i] > 1 && lds[i] > 1) {
                result = Math.max(result, lis[i] + lds[i] - 1);
            }
        }
        return result;
    }
}

Complexity Analysis

Time Complexity: O(n log n)

Computing LIS processes n elements, each requiring a binary search on the tails array. The tails array has at most n elements, so each binary search is O(log n). Total for LIS: O(n log n). Same for LDS: O(n log n). The combination step is O(n). Overall: O(n log n).

With n ≤ 1000: approximately 1000 × 10 ≈ 10,000 operations — nearly 100× faster than the O(n²) approach.

Space Complexity: O(n)

We use two arrays of size n (LIS and LDS), plus a tails array of at most n elements. Total auxiliary space is O(n).