Pythonで線形時間でサイズ3のソートされたサブシーケンスを検索します

これを解決するには、次の手順に従います-

• n：=Aのサイズ
• 最大：=n-1、最小：=0
• 小さい：=サイズ1000の配列で、0で埋める
• 小さい[0]：=-1
• 1からnの範囲のiについては、
  • A [i] <=A [minimum]の場合、
    • 最小：=i
    • 小さい[i]：=-1
  • それ以外の場合、
    • 小さい[i]：=最小
• より大きい：=サイズ1000の配列で、0で埋める
• great [n-1]：=-1
• n-2から-1の範囲のiについては、1ずつ減らします。
  • A [i]> =A [maximum]の場合、
    • 最大：=i
    • great [i]：=-1
  • それ以外の場合、
    • great [i]：=maximum
• 0からnの範囲のiについては、
  • small [i]が-1と同じでなく、greater [i]が-1と同じでない場合、
    • return A [smaller [i]]、A [i]、A [greater [i]]
• 「何も」を返さない

例

理解を深めるために、次の実装を見てみましょう-

def find_inc_seq(A):
   n = len(A)
   maximum = n-1
   minimum = 0
   smaller = [0]*10000
   smaller[0] = -1
   for i in range(1, n):
      if (A[i] <= A[minimum]):
         minimum = i
         smaller[i] = -1
      else:
         smaller[i] = minimum
   greater = [0]*10000
   greater[n-1] = -1
   for i in range(n-2, -1, -1):
      if (A[i] >= A[maximum]):
         maximum = i
         greater[i] = -1
      else:
         greater[i] = maximum
   for i in range(0, n):
      if smaller[i] != -1 and greater[i] != -1:
         return A[smaller[i]], A[i], A[greater[i]]
   return "Nothing"
arr = [13, 12, 11, 6, 7, 3, 31]
print(find_inc_seq(arr) )

入力

[13, 12, 11, 6, 7, 3, 31]

出力

(6, 7, 31)