intの配列があるとしましょう：a = {2,4,3,5}
そして、k = 3です。
配列の順序を変更できないk（3）個のサブ配列に配列aを分割できます。すべてのサブアレイ間の最大合計ができるだけ低くなるように、各サブアレイの合計はできるだけ低くする必要があります。
上記のソリューションの場合、これにより{2、4}、{3}、{5}が得られ、最大合計は6（4 + 2）になります。
この場合、最大合計は7（4 + 3）であるため、間違った答えは{2}、{4、3}、{5}になります。
すべてのintを合計し、結果のサブ配列の量で除算することにより、配列全体の平均を計算する欲張りアルゴリズムを作成してみました。したがって、上記の例では、これは14/3 = 4（整数除算）を意味します。次に、平均数よりも小さい限り、カウンターに数を合計します。次に、残りのサブ配列について再計算します。
私のソリューションは適切な近似を提供し、ヒューリスティックとして使用できますが、常に正しい答えが得られるとは限りません。
誰かが私にすべての場合に最適な解決策を与え、O（N²）よりも優れているアルゴリズムを手伝ってくれるでしょうか？およそO（n log n）のアルゴリズムを探しています。
前もって感謝します！
この問題を解決するために二分探索を使用することができます。
したがって、すべてのサブ配列の最大値が、であると仮定すると、x各サブ配列の合計が最大で、以下になるように、O（n）の各サブ配列を貪欲に選択できますx。すべてのサブ配列を作成した後、サブ配列の数が、以下の場合k、x1つの可能な解決策がありxます。そうでない場合は、を増やします。
擬似コード：
int start = Max_Value_In_Array;
int end = Max_Number;
while(start <= end)
int mid = (start + end)/2;
int subSum = 0;
int numberOfSubArray = 1;
for(int i = 0; i < n; i++){
if(subSum + data[i] > mid){
subSum = data[i];
numberOfSubArray++;
}else{
subSum += data[i];
}
}
if(numberOfSubArray <= k)
end = mid - 1;
else
start = mid + 1;
kとの時間計算量O（n log k）は、可能な最大の合計です。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加