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

Question

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

我正在考虑制作两个功能； 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)

如果您想进一步改进编码，也许可以尝试编辑程序，使其打印出所有最长的序列（即，如果有 2 个最长的不同序列，则打印出它们，而不仅仅是第一个）。

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

Longest consecutive sequence where each element is less than 3

python

algorithm

sequence

time-complexity