問題タブ [kadanes-algorithm]
For questions regarding programming in ECMAScript (JavaScript/JS) and its various dialects/implementations (excluding ActionScript). Note JavaScript is NOT the same as Java! Please include all relevant tags on your question; e.g., [node.js], [jquery], [json], [reactjs], [angular], [ember.js], [vue.js], [typescript], [svelte], etc.
c++ - 連続部分配列の最大合計を見つけるためのこの再帰アルゴリズムには利点がありますか?
目的: 以下の連続部分配列で最大和を見つけるためのアルゴリズムを評価します。
注：C++で書かれています
Kadane が動的計画法を使用してうまく解決した問題を調べていたとき、私はそれを解決する独自の方法を見つけるだろうと考えました。配列の両端を短くすることで合計を大きくできるかどうかに応じて、一連の再帰呼び出しを使用してこれを行いました。下記参照。
Kadane のアルゴリズムが O(n) 時間かかることは理解しています。アルゴリズムの Big O の計算に問題があります。それもO(n)でしょうか？O(n) を使用して合計を計算するため、その後のすべての呼び出しは同じ時間を使用します。私のアルゴリズムは Kadane のアルゴリズムよりも有利ですか? Kadane のアルゴリズムはどのような点で優れていますか?
arrays - 同じ開始要素と終了要素を持つ部分配列の合計の最大値
文字列と各文字の値を与えるオンラインテストの問題がありました。各文字の値は [-10, 10] の範囲です。問題は、同じ文字で開始および終了し、最大値を持つ部分文字列を見つけることでした。この問題は、文字を値に置き換えた後、部分配列の最大合計問題の拡張バージョンに簡単に縮小されます。制約は、開始値と終了値が同じになることです。私は素朴な解決策を思いつきましたが、十分ではありませんでした。Kadane のアルゴリズムまたは時間の複雑さが改善された他のアルゴリズムでこれを解決する方法を誰か教えてもらえますか?