「プログラミングパール」のコラム8にあります。最大部分配列の問題があります。
問題 ：
入力は n 個の浮動小数点数のベクトル x です。出力は、入力の連続するサブベクトルで見つかった最大合計です。問題の定義を完成させるために、すべての入力が負の場合、最大合計部分ベクトルは合計がゼロの空のベクトルであると言います。
最も効率的なソリューション:
maxsofar = 0
maxendinghere = 0
for i = [0, n)
maxendinghere = max(maxendinghere+x[i], 0)
maxsofar = max(maxsofar, maxendinghere)
このコラムには演習があります。 負の数の配列の最大サブベクトルを、空のサブベクトルの合計であるゼロと定義しました。代わりに、最大のサブベクトルを最大の要素の値として定義したとします。さまざまなプログラムをどのように変更しますか？
この演習について 2 つの質問があります (1) 「代わりに、最大のサブベクトルを最大の要素の値として定義したと仮定してください」ということでちょっと混乱しています。負の数の配列の最大サブベクトルが配列内の最大の要素になることを意味しますか?
例: 配列: [-1 -2 -3]、最大サブベクトル: -1 配列: [-1 2 3]、最大サブベクトル: [2 3]
このダミーの質問で申し訳ありません。英語は私の素朴な言語ではありません。
(2) 著者は、「割り当て maxsofar=0 を maxsofar = -infinity に置き換えます」という解決策を示しました。質問に対する私の理解に基づいて、この解決策は正しくないようです。
例: Array : [-1 -2 -3]、答えは -1 である必要があります。しかし、解決策によると、それは 0 です。
ありがとう、