每个元素小于3的最长连续序列

Question

我以前见过一些最长的连续序列问题，比如查找递增子序列。我现在正在努力进一步发展我的技能。给定一个整数数组，我想找到一个最长的连续序列，其中各个子序列中所有元素的差值小于一个给定的数字，例如3。一个例子是[10,11,12,15,13]，其中只有前三个元素满足条件。此外，我还想返回给定数组中第一个和最后一个元素的索引。

我想做两个函数；get_first_element(arr)和get_last_element(arr)。

def get_last_ele(arr):
    longest_seq = 0
    last_ele = 0

    max_difference = 3

    for i in range (0, len(arr)):

        max_ele_seq = arr[i]
        min_ele_seq = arr[i]
        _count = 0
        _last_ele = i
        for j in range(i,len(arr)-i+1):
            ele_j = arr[j]
            if ele_j > max_ele_seq:
                max_ele_seq = ele_j
            if ele_j < min_ele_seq:
                min_ele_seq = ele_j
            if abs(max_ele_seq - min_ele_seq) > max_difference:
                break

            last_ele = j
            _count += 1

        if _count > longest_seq:
            longest_seq = _count
            last_ele = last_ele

    return last_ele     

我觉得我可以重新使用这段代码来获得第一个元素，但那将是多余的，以有两个相似的函数。是否有可能在一个函数中实现所有这些功能？在时间复杂性方面是否有更好的解决方案？

Answer 1

def get_longest_sequence(arr):
    """
    Prints out the longest sequence, its length, and the index of its first and last elements

    arr: list of numbers
"""

    longest_seq_length = 0
    last_ele_index_of_longest_seq = 0
    max_difference = 3

    for i in range(0, len(arr)): 

        max_ele_seq = arr[i]
        min_ele_seq = arr[i]

        count = 0

        for j in range(i, len(arr)):

            ele_j = arr[j]
            if ele_j > max_ele_seq:
                max_ele_seq = ele_j
            elif ele_j < min_ele_seq:
                min_ele_seq = ele_j

            if max_ele_seq - min_ele_seq > max_difference: # no need for abs() since max always larger than min
                break

            last_ele_index = j
            count += 1

        if count > longest_seq_length:
            longest_seq_length = count
            last_ele_index_of_longest_seq = last_ele_index
            # no need for last_ele = last_ele, it does nothing, merely reassigns itself

    longest_seq = arr[(last_ele_index_of_longest_seq - longest_seq_length + 1):(last_ele_index_of_longest_seq + 1)]
    print(f"The longest sequence found: {longest_seq}")
    print(f"Its length: {longest_seq_length}")
    print(f"Index of first element (with regards to arr): {last_ele_index_of_longest_seq - longest_seq_length + 1}")
    print(f"Index of last element: {last_ele_index_of_longest_seq}")

arr = [10,11,12,15,13]
get_longest_sequence(arr)

如果你想进一步改进你的编码，也许可以尝试编辑程序，使它能够打印出所有最长的序列（例如，如果有两个最长的不同序列，则打印出两个序列，而不是只打印出第一个序列）。