Как получить строго возрастающую последовательность, удалив из массива не более одного элемента?

Question

Ответ можно написать и на javascript.

Учитывая последовательность целых чисел в виде массива, определите, можно ли получить строго возрастающую последовательность, удалив из массива не более одного элемента.

К примеру:

1. Для $sequence = [1, 3, 2, 1] вывод должен быть

   almostIncreasingSequence(sequence) = false;
   

2. Для $sequence = [1, 3, 2] вывод должен быть

   almostIncreasingSequence(sequence) = true;
   

Вы можете удалить 3 из массива, чтобы получить строго возрастающую последовательность [1, 2]. В качестве альтернативы вы можете удалить 2, чтобы получить строго возрастающую последовательность [1, 3].

3. Для $sequence = [1, 2, 3, 4, 5, 6] вывод должен быть

   almostIncreasingSequence(sequence) = true;
   

Возвращает true, если можно удалить один элемент из массива, чтобы получить строго возрастающую последовательность, иначе верните значение false.

Пытаюсь решить следующим путем:

function almostIncreasingSequence($sequence) {
    $r = 0;
    for ($i = 0, $prev = -1, $cnt = count($sequence)-2; $i < $cnt; $i ++)
    {
        if(!isset($sequence[$i]))
            continue;
        if ($sequence[$i] >= $sequence[$i+1])
        {
            $r ++;
            $i = $prev;
            unset($sequence[$i+1]);
        }
    }
    return $r < 1;
}

var_dump(almostIncreasingSequence([1, 2, 3])); //true
var_dump(almostIncreasingSequence([1, 3, 2, 1])); //Должен быть false, вместо этого получаю бесконечный цикл

Внимание вопрос: Как правильно решить эту задачу ?

Answer 1

Решил таким образом:

Если другой ответ будет более элегантным и оптимальнее то приму eго

function almostIncreasingSequence($sequence) {
    if(!$sequence)
        return NULL;
    $foundOne = false;

    for ($i = -1, $j = 0, $k = 1; $k < count($sequence); $k++)
    {
        $deleteCurrent = false;
        if ($sequence[$j] >= $sequence[$k])
        {
            if ($foundOne)
            {
                return false;
            }
            $foundOne = true;
            if ($k > 1 && $sequence[$i] >= $sequence[$k])
            {
                $deleteCurrent = true;
            }
        }
        if (!$foundOne)
        {
            $i = $j;
        }
        if (!$deleteCurrent)
        {
            $j = $k;
        }
    }
    return true;
}

var_dump(almostIncreasingSequence([1,3,2]));//true
var_dump(almostIncreasingSequence([1,3,2,1]));//false
var_dump(almostIncreasingSequence([2,1,2,3]));//true

Answer 2

Использую тот же подход, что и в https://ru.stackoverflow.com/a/479325/178988 - префиикс и суффикс являются возрастающими последовательностями, а место стыка надо дополнительно проверить на удаление элемента (может быть лишний центральный, либо в отсутствии центрального один из крайних). Асимптотика линейная.

function process(a) {
  var l, r, i;
for (l = 0; a[l] < a[l+1]; ++l);
  if (l >= a.length - 1) return a;
  for (r = a.length-1; a[r-1] < a[r]; --r);
function check(a, b) {
    return a == null || a < b || b == null;
  }
switch (r-l) {
    case 1:
      if (check(a[l-1], a[r])) {
        i = l;
      } else if (check(a[l], a[r+1])) {
        i = r;
      } else {
        return null;
      }
      break;
    case 2:
      if (check(a[l], a[r])) {
        i = l + 1;
      } else {
        return null;
      }
      break;
    default:
      return null;
  }
a.splice(i, 1);
  return a;
}
console.log(process([1,2,3]))
console.log(process([1,2,3,0]))
console.log(process([9,1,2,3,0]))
console.log(process([1,2,9,3,4]))
console.log(process([1,2,9,0,3,4]))
console.log(process([]))
console.log(process([-1,0,-5]))