2
配列が[2、3、3、6、7]の場合、ソートされませんが、それはあなたが望むならばそれです。 2 + 3 + 6 = 11および7 + 3 = 10であるため、結果のサブアレイは[2,3,6]および[7,3]になるように、配列内のすべての要素を使用して2つのサブ配列を検索します。要素の合計が等しいか近い要素の配列から2つの部分配列を見つけよう
結果として得られるサブアレイの和は等しい必要はありませんが、可能な限り近くになければなりません。
私の最初のアプローチは、この要素を降順にソートし、要素を配列の両端から取り出すことでした。
ありがとうございます、ありがとう、ありがとう。
ここではヒントがあります： 'S'を配列全体の合計とすると、この問題は' S/2'に近い部分配列を探すのと同じです。できるだけ。 – kevmo314
はい、私はそれを考えましたが、もし最後の要素が超大だとすればどうでしょうか。すでに似たようなことをするための確立されたアルゴリズムがありますか？ – luis
これは問題ありません。「S/2」より厳密に小さいサブアレイを見つけるだけで十分です。問題は「整数の配列を与え、合計が最大になるようなサブアレイを選んでください」ここで、k = S/2である。これは、共通のCS問題と非常によく似ているはずです。 – kevmo314