[Algorithm] almostIncreasingSequence

Problem

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

• For sequence = [1, 3, 2, 1], the output should be
  almostIncreasingSequence(sequence) = false;

  There is no one element in this array that can be removed in order to get a strictly increasing sequence.

• For sequence = [1, 3, 2], the output should be
  almostIncreasingSequence(sequence) = true.

  You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

• [input] array.integer sequence

  Guaranteed constraints:
  2 ≤ sequence.length ≤ 105,
  -105 ≤ sequence[i] ≤ 105.

• [output] boolean

  Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

Solution

def almostIncreasingSequence(sequence):
count_decreasing_sq = 0

for i in range(len(sequence) - 1):
if count_decreasing_sq > 1:
return False
elif sequence[i] > sequence[i+1]:
count_decreasing_sq += 1
if i >= 1 and sequence[i+1] <= sequence[i-1]:
if len(sequence) - 2 > i and sequence[i+2] <= sequence[i]:
count_decreasing_sq += 1

return count_decreasing_sq <= 1

*count_decreasing_sq : 내림차순으로 이어지는 흐름의 개수를 저장하는 변수입니다. 이 변수를 통해 정상적인 흐름으로 진행하고 있는지를 판단합니다.

문제에서 하나의 수는 제거할 수 있다고 했으므로, 한 번의 비정상적은 흐름은 감수합니다. 만약 비정상적인 흐름이 2번 이상 발견된다면 False를 반환합니다.

 공감

sns신고