試験の準備中にこの問題が発生しました。
数値a1、...、anおよびb1、....、bnの2つの配列が与えられ、各数値は0または1であり、、ai + ai + 1のような最大スパン(i、j)を見つけるための最速のアルゴリズム+ .... + aj = bi + bi + 1 + ....+bjまたはそのようなスパンがないことを報告します。
(A)ハッシュが許可されている場合、O(3 ^ n)およびomega(2 ^ n)の時間がかかります。
(B)キー比較モードでO(n ^ 3)とomega(n ^ 2.5)と時間を取ります
(C)シータ(n)の時間とスペースを取ります
(D)2n個の要素の合計が偶数の場合にのみO(平方根(n))の時間がかかります。