查找最长子数组

Question

给定一个整数数组，最长的子数组的长度为不超过两个不同值，以使不同值相差不超过1？

示例：

arr = [0,1,2,1,2,3]

最大的此类子数组的长度为4：[1,2,1,2]。

arr = [1, 1, 1, 3, 3, 2, 2]

最大的此类子数组的长度为4：[3、3、2、2]。值1和3相差大于1，因此[1、1、1、3、3]无效。

Answer 1

我认为没有比O(n)更好的解决方案。

您未指定任何语言，因此伪代码应如下所示（我最终编写了python脚本：]

a = [1, 1, 1, 3, 3, 2, 2]
max_solution_arr = []
cur_sol_arr = []
max_length = 0
cur_len = 0

def min_(a, a_i):
  if len(a) == 0:
      return a_i
  return min(a)

def max_(a, a_i):
  if len(a) == 0:
      return a_i
  return max(a)
for i, a_i in enumerate(a):
    if i == 0:
        cur_sol_arr.append(a_i)
        cur_len += 1
    else:
        if (abs(a[i] - min_(cur_sol_arr, a[i])) <= 1) and (abs(a[i] - max_(cur_sol_arr, a[i])) <= 1):
            # solution extend
            cur_sol_arr.append(a_i)
            cur_len += 1
        else:
            # we need to break, update solution
            if cur_len > max_length:
                max_length = cur_len
                max_solution_arr = cur_sol_arr[:] # make a copy here
                cur_sol_arr = [a_i] # delete
                cur_len = 1
# residual

if cur_len > max_length:
   max_length = cur_len
   max_solution_arr = cur_sol_arr # make a copy here

print(max_solution_arr)

想法是，您将保留一个数组，在其中继续追加元素，除非不满足条件（> 1个差），在这种情况下，如果当前解决方案更好，则将当前数组与max解进行比较只需更新最大解决方案即可。