Найдите самый длинный подмассив

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 (1), время O (n). Мы можем получить ответ для последовательности, оканчивающейся на A[i], посмотрев на лучшую последовательность, заканчивающуюся на A[i-1], которая, возможно, включает более высокие элементы, и лучшую последовательность, заканчивающуюся на A[i-1], которая, возможно, включает более низкие элементы.

JavaScript код:

function f(A){
  if (A.length < 2)
    return A.length;
    
  let best = 1;
  let bestLower = 1;
  let bestHigher = 1;
  
  for (let i=1; i<A.length; i++){
    if (A[i] == A[i-1]){
      bestLower = bestLower + 1;
      bestHigher = bestHigher + 1;
    
    } else if (A[i] - 1 == A[i-1]){
      bestLower = 1 + bestHigher;
      bestHigher = 1;
    
    } else if (A[i] + 1 == A[i-1]){
      bestHigher = 1 + bestLower;
      bestLower = 1;
    
    } else {
      bestLower = 1;
      bestHigher = 1;
    }

    best = Math.max(best, bestLower, bestHigher);
  }
  
  return best;
}

arrays = [
  [0, 1, 2, 1, 2, 3], // length = 4; [1,2,1,2]
  [1, 2, 3, 4, 5], // length = 2; [1,2]
  [1, 1, 1, 3, 3, 2, 2] // length = 4; [3,3,2,2]
];

for (let arr of arrays){
  console.log(JSON.stringify(arr));
  console.log(f(arr));
}

Answer 2

Я не думаю, что есть какое-либо решение лучше, чем 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 разница), в этом случае сравните текущий массив с максимальным решение, если текущее решение лучше, просто обновите максимальное решение.