5 Best Ways to Find Length of Longest Increasing Then Decreasing Sublist in Python

Rate this post

πŸ’‘ Problem Formulation: The task is to identify the longest sublist within a given list of integers where the sublist first strictly increases and then strictly decreases. For example, given the input [5, 2, 8, 6, 3, 6, 9, 5], the desired output would be 5, representing the length of the sublist [2, 8, 6, 3].

Method 1: Dynamic Programming

This method involves using dynamic programming to record the lengths of the longest increasing and decreasing subsequence at each index. We perform a forward traversal to find the longest increasing subsequence and a backward traversal to find the longest decreasing subsequence, and then we find the maximum sum of lengths minus one.

Here’s an example:

def find_longest_bitonic_sublist(arr):
    n = len(arr)
    inc = [1] * n
    dec = [1] * n
    
    for i in range(n):
        for j in range(i):
            if arr[i] > arr[j]:
                inc[i] = max(inc[i], inc[j] + 1)
    
    for i in reversed(range(n)):
        for j in range(i + 1, n):
            if arr[i] > arr[j]:
                dec[i] = max(dec[i], dec[j] + 1)
    
    max_len = 0
    for i in range(n):
        max_len = max(max_len, inc[i] + dec[i] - 1)
    
    return max_len

print(find_longest_bitonic_sublist([5, 2, 8, 6, 3, 6, 9, 5]))

The output of this code snippet:

5

This code defines a function find_longest_bitonic_sublist that calculates the length of the longest bitonic sublist in the input array. It uses two temporary arrays, inc and dec, to store the lengths of the longest increasing and decreasing sublists ending at each index, then iterates to find the maximum sum of lengths, subtracting one to account for the peak element being counted twice.

Method 2: Space Optimized Dynamic Programming

Leveraging dynamic programming with space optimization, this method reduces the space complexity by using one pass and keeping track of the maximum legths ‘on the fly’ without storing them for all indices, minimizing space usage.

Here’s an example:

def max_length_bitonic(arr):
    if not arr: return 0
    max_len, incr, decr = 1, 1, 0
    
    for i in range(1, len(arr)):
        if arr[i - 1]  arr[i]:
            decr += 1
            max_len = max(max_len, incr + decr)
        else: 
            incr, decr = 1, 0
    
    return max(max_len, incr + decr)

print(max_length_bitonic([5, 2, 8, 6, 3, 6, 9, 5]))

The output of this code snippet:

5

The max_length_bitonic function traverses the list once, maintaining two counters, incr for counting increasing elements and decr for decreasing elements. Rather than storing lengths at all positions, it updates the max_len during the traversal as soon as a bitonic sequence ends.

Method 3: Using Stack

This method employs a stack to keep track of potential candidates for the longest bitonic sublist by maintaining a stack of indices where the sequence increases or decreases. Then the maximum length is calculated based on this processed stack.

Here’s an example:

def bitonic_stack(arr):
    stack = []
    max_len = 0
    
    for i, num in enumerate(arr):
        while stack and arr[stack[-1]] >= num:
            max_len = max(max_len, i - stack.pop())
        stack.append(i)
    
    return max(max_len, len(arr) - stack[0]) if stack else len(arr)

print(bitonic_stack([5, 2, 8, 6, 3, 6, 9, 5]))

The output of this code snippet:

5

The bitonic_stack function sequentially pushes indices onto a stack as long as the sequence is increasing. When a decrease occurs, it calculates the possible lengths by popping from the stack and updates the max_len accordingly, ensuring the longest bitonic length is found.

Bonus One-Liner Method 4: List Comprehensions

This concise one-liner uses Python’s list comprehensions to calculate the longest bitonic sublist in an elegant and brief way, sacrificing some readability for brevity.

Here’s an example:

arr = [5, 2, 8, 6, 3, 6, 9, 5]
print(max(len(arr[:i][::-1]) + len(arr[i + 1:j][::-1]) + 1
          for i in range(len(arr)) for j in range(i + 2, len(arr))
          if max(arr[:i] + arr[j:], default=arr[i]) == arr[i]))

The output of this code snippet:

5

This one-liner iterates over all possible peak elements of bitonic sublists and sums the lengths of the increasing and decreasing parts, accounting for the sublist’s boundaries, to find the overall maximum length of a bitonic sublist within the list.

Summary/Discussion

  • Method 1: Dynamic Programming. Good for a clear and extendable implementation. However, it has a higher space complexity due to the use of two additional arrays. This method could become inefficient for very large lists.
  • Method 2: Space Optimized Dynamic Programming. Optimizes space by eliminating the extra arrays, ideal for memory-constrained environments. However, the method may be slightly less intuitive to understand and harder to debug.
  • Method 3: Using Stack. Provides an interesting alternative using data structures, can be more easily adapted to stream processing. However, it might not be as straightforward and requires careful consideration of stack operations.
  • Bonus One-Liner Method 4: List Comprehensions. Offers a compact solution appealing to those who favor Pythonic brevity. Nevertheless, it comes at the cost of readability and might be impractical for complex operations or modification.