最大連続和を求めると、点を含むセグメントが見つかる

Question

1）整数の配列（負と正の値）を与えられたとき - 最大の連続する和を返す最も効率的なアルゴリズムは何か？

a）私はDynamic Programingでこれを解決すると考えましたが、複雑さはO（n^2）です。別の方法がありますか？

b）無限の整数を入力した場合はどうなりますか？現在の最大連続合計を出力する方法はありますか？私はそうは思わない。

2）与えられたセグメント：開始点、昇順、昇順でセグメントの配列[開始、終了]（経過可能） とポイント。

このポイントを含むセグメント/このポイントを含むすべてのセグメントを返す最も効率的なアルゴリズムは何ですか？ 私は、この点の前で始まる最初のセグメントを、左右に移動しようとするよりも早くhitするためにbinarySearchを使用すると考えました。

他のアイデアはありますか？ 1については

Answer 1

）私は

Answer 2

）限り、あなたはWRTの終点を注文すると仮定することはできませんよう（あなたのアプローチは悪くないと思う2の場合）、N（Oに

を働いているalgorithm）があります1）合計がゼロ以下にならない限り、連続加算を続ける方が常に良いです。したがって、配列を左から右に1回（つまり線形のランタイムアルゴリズムを使用して）渡し、現在の連続した総和と最大の連続した総和を覚えておいて、現在の合計が最大の合計より大きくなるたびに更新します。

したがって、配列トラバーサルのどの時点でも、今までの最大合計が何であるかを言うことができます。したがって、このアルゴリズムを（無限の）入力ストリームに使用することもできます。

2）はい、バイナリ検索がうまくいきます。しかし、私が問題を正しく理解していれば、一番右のセグメント（ポイントに最も近いセグメント）から始めて、セグメントを左にトラバースすることができます。もちろん、最悪の場合のランタイムはセグメント数では線形ですが、平均は対数でなければなりません。