最大円形サブアレイ

Question

これは、Jeff Ericksonによる本アルゴリズムからの質問です。

Aが円列アレイであるとします。この設定では、「隣接サブアレイ」は、間隔A [i ..j]または接頭辞A [i ..N]・A [1 ..j]のいずれかでもよい。最大の合計で隣接するサブアレイを見つけるアルゴリズムを説明し分析します。 入力配列は実数で構成されています。

私のアプローチ：

2つの可能性があります

1）包装しない（カダンのアルゴリズムを使用することができます）

2）折り返し（すなわち、サブアレイの開始インデックスは終了インデックスより大きい）（この場合は疑いがある）

今すぐ最大2例を返します。

2番目のケースでは、インターネットを検索すると、証明なしのアプローチがありました。

アプローチは、最小の合計でサブアレイを見つけ、それをアレイ全体の合計から減算することです（つまり、合計（a） - min_subarray_sum（a））。この解決策はどのように正しいですか？

2番目の場合で使用される方法のためのリンク： https：// www。 geeksforgeeks.org/maximum- contigure-circular-sum/

Answer 1

$ a $ あなたの配列になる、 $ b $ $ a $ は、 $ \ sum_ {b} b $ を最大化し、 $ c $ $ a $ のすべての要素を含むサブアレイになります。 $ B $ 。 $ c $ も円形のサブアレイです。

$ \ sum_ {a \ \ sum_ {b} b + \ sum_ {c \ in c} c $ これは、 $ \ sum_ {c=sum_ {a \ in \ \ sum_ {b \ in b} b} b $ です。 $ \ sum_ {a \ in a} $ は定数（WRT $ b $ ）です。 $ b $ の最大化 $ \ sum_ {b} b $ 、 $ c $ の最小化 $ \ sum_ {c} c} c $ 。

また、

$ b $ 、 $ c $ のうちの少なくとも1つは、円形だけでなくそのため、 $ o（n）$ 時間。

にあります。