longestMonotone.py

def longest_monotone_subset(points, increasing=True):
    n = len(points)
    
    # Initialize an array to store the length of longest monotone sequence ending at each index
    longest_lengths = [1] * n
    
    # Initialize an array to store the previous index in the longest monotone sequence
    prev_indices = [-1] * n
    
    # Choose the comparison operator based on whether we are looking for increasing or decreasing sequences
    compare = lambda a, b: a <= b if increasing else a >= b
    
    # Find longest monotone sequence lengths
    for i in range(1, n):
        for j in range(i):
            if compare(points[i][1], points[j][1]) and longest_lengths[i] < longest_lengths[j] + 1:
                longest_lengths[i] = longest_lengths[j] + 1
                prev_indices[i] = j
    
    # Find the maximum length of longest monotone sequence
    max_length = max(longest_lengths)
    
    # Find all indices of points that are part of the longest monotone sequence
    longest_indices = [i for i, length in enumerate(longest_lengths) if length == max_length]
    
    # Construct longest monotone sequences
    longest_subsets = []
    for index in longest_indices:
        monotone_subset = []
        while index != -1:
            monotone_subset.append(points[index])
            index = prev_indices[index]
        longest_subsets.append(list(reversed(monotone_subset)))
    
    return longest_subsets

# Example usage:
points = [(-5,0), (-3,5), (0,3), (1,-4), (4,1), (5,6)]

# Find longest increasing subsets
longest_increasing_subsets = longest_monotone_subset(points, increasing=True)
print("Longest Decreasing Subsets according to y-value:")
for subset in longest_increasing_subsets:
    print(subset)

# Find longest decreasing subsets
longest_decreasing_subsets = longest_monotone_subset(points, increasing=False)
print("\nLongest Increasing Subsets according to y-value:")
for subset in longest_decreasing_subsets:
    print(subset)