最大サブアレイ問題によく似た問題を解決する必要があります。平均が k より大きい最大の部分配列を見つけなければなりません。次のトリックを考えました。サイズ n の配列 A[] を B[i] = A[i] - k の B[] に変換できます。したがって、平均は >0 でなければなりません。しかし、ゼロより大きい平均は、単純に合計がゼロより大きいという意味ではありませんか? したがって、Kadane のアルゴリズムを直接適用できます。私は正しいですか？(常に 1 つの正の値があるという制約の下で)
質問する
1351 次
2 に答える
4
いいえ、kadane のアルゴリズムは最大の合計を持つ部分配列を見つけます...同じ問題を解決する必要があります。これまでのところ、上記のように配列 B を作成し、配列 B の部分和を含む配列 C を作成すると、探している最大間隔 (i,j) が同じ数になることがわかりました。私とjのために!!! 例えば：
配列 A は: 1 10 -1 -1 4 -1 7 2 8 1 ...そして与えられた k は 5 で、配列 B は: -4 5 -6 -6 -1 -6 2 -3 3 -4配列 C は:-4 1 -5 -11 -12 -18 -16 -19 -16 -20 なので、探している部分配列は [7,2,8] で、長さは 3 で、最初と-16 である最後の要素!!!!
編集：O（n）またはO（n * logn）アルゴリズムを検索していることを忘れていました.... @lets_solve_itあなたは正しいですが、あなたのアルゴリズムはO（n ^ 2）であり、これは非常に大きなものです処理したいデータ。私はそれをC ++の関数マップで解決しようとしています。これはハッシュテーブルのようなものです。ここでは、配列 C の要素がインデックスと直接関係しているため、これは正しい方向です。また、私たちの教授は、別の可能な解決策は、配列 C を再度作成し、(特別な?) ピボットを使用してクイックソートを行うことだと言いました....しかし、クイックソートに何を期待するのか完全には理解できません。
于 2012-11-20T09:42:31.350 に答える
2
@panos7:
配列 C (部分和配列) を作成した後、Ci と Cj の 2 つの値を求めます。
Cj>=Ci であり、(ji) は可能な限り「大きく」なります。(じ) --> MAX.
その後、ジを返します。
あなたの例では、 -16>=-18 なので、 ji=9-6=3 を返しました
これが正解です！
于 2012-11-22T22:05:51.070 に答える