トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

最長増加部分列

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴

最長増加部分列

  英語の解説

  日本語の解説

  AOJの関連する問題

  問題設定

まずはWikipediaの記述から...

 In the first 16 terms of the binary Van der Corput sequence
 
 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
 a longest increasing subsequence is
 
 0, 2, 6, 9, 11, 15.
 This subsequence has length six; the input sequence has no seven-member increasing subsequences. The longest increasing subsequence in this example is not unique: for instance,
 
 0, 4, 6, 9, 11, 15 or 0, 4, 6, 9, 13, 15
 are other increasing subsequences of equal length in the same input sequence.

van der Corput 列の最初の16個の数値

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

において、最長増加部分列は

0, 2, 6, 9, 11, 15.

この部分列は長さ6である、ということは(当たり前だが)7要素の増加部分列を持たない。この例における最長増加部分列は一意ではない、例えば

0, 4, 6, 9, 11, 15 もしくは 0, 4, 6, 9, 13, 15

は入力された同一の列内で等しい長さを持つ他の増加部分列であると言える

  アルゴリズム

線形探索版のプログラム - O(N^2)

  • 与えられる配列を arr[n]、最長増加部分列をlis[n] であるとする
  • arrlis の出来上がりは以下のようになる
    • 上がarrayで下がlis
9 5 2 8 7 3 1 6 4 5
1 1 1 2 2 2 1 3 3 4

要はlisの配列にはそのインデックスまでの配列における最長増加部分列の部分列の長さが入るということ

動的計画法版のプログラム - O(N^2)

  • 準備中

二分探索版のプログラム - O(N log N)

  • 与えられる配列を arr[n]、最長増加部分列をtail[n] であるとする
  • arrtail の出来上がりは以下のようになる
    • 上がarrayで下がtail
    • Rubyなのでnilが入っているが、0でもよいだろう
9 5 2 8 7 3 1 6 4 5
1 3 4 5 nil nil nil nil nil nil

こちらのほうが早く、tailに実際の最長増加部分列が入るため、より良いアルゴリズムと言えそうだ。

  最長増加部分列を考える利点

  • 先ほどの部分列は昇順で並んでいる
  • これで得た最長増加部分列をもとに、残りの要素をどんだけ動かせばソートされるかわかる

  サンプルプログラム

線形探索版のプログラム - O(N^2)

lines = <<'EOS'
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
EOS

#lines = $stdin.read
array = lines.split("\n")

def get_lis(arr)
  lis_arr = Array.new(arr.length){1}
  length = 1

  puts arr.to_s
  puts lis_arr.to_s

  for i in 1...arr.length
    for j in 0...i
      lis_arr[i] = lis_arr[j] + 1 if arr[j] < arr[i] and lis_arr[i] < (lis_arr[j]+1)
    end
  end

  puts lis_arr.to_s
  lis_arr.max
end

puts get_lis(array[0].split(" ").map(&:to_i).to_a)
  • 探索対象の配列を i 回ループし、その中で j 回ループするので、当然ながら 計算量が O(n^2) になる、遅い

動的計画法によるプログラム - O(N^2)

  • 準備中

二分探索版のプログラム - O(N log N)

#
# http://www.csegeek.com/csegeek/view/tutorials/algorithms/dynamic_prog/dp_part6.php
#

lines = <<'EOS'
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15
EOS

#lines = $stdin.read
array = lines.split("\n")

def ceil_index(array, l, r, key)
  while r-l > 1
    m = l + (r-l)/2
    if array[m] >= key
      r = m
    else
      l = m
    end
  end
  r
end

def get_lis(arr)

  tail = Array.new(arr.length)
  len = 1
  tail[0] = arr.first

  for i in 1...arr.length
    if arr[i] < tail[0]
      tail[0] = arr[i]
    elsif arr[i] > tail[len-1]
      # v[i] extends largest subsequence
      tail[len] = arr[i]
      len = len + 1
    else
      # option(a): use binary search
      # but, ruby's Array#bsearch_index requires
      # all array's elements sorted
      idx = tail[0..i].compact.bsearch_index do |x|
        x >= arr[i]
      end

      # option(b): implement binary search yourself
      #idx = ceil_index(tail, -1, len-1, arr[i])
      tail[idx] = arr[i]
    end
  end
  len
end

puts get_lis(array[0].split(" ").map(&:to_i).to_a)

  • 探索対象の配列を i 回ループするのは同じだが、その中で二分探索するので、計算量が O(NlogN) になる、これは結構早い
お名前: コメント: