免責事項: これは割り当て用です。私は明示的なコードを求めているのではなく、コードのエラーを修正できるように、関連するアルゴリズムを理解するのに十分な助けを求めているだけです。
さて、あなたはおそらく部分配列の最大化問題に精通しているでしょう: 配列内の連続する整数の最大ブロックを計算して返します。簡単ですが、この割り当てでは、O(n^3)、O(n^2)、O(n log n) という 3 つの異なる複雑さで実行する必要があります。最初の 2 つは問題なく取得できましたが (ブルート フォース)、3 番目は頭痛の種です..文字通り。
アルゴリズムがどのように機能するかを理解しています。配列は関数に渡され、再帰的に半分に分割され、個々のコンポーネントを比較して各半分の最大サブ配列を見つけます。次に、最大の部分配列は完全に左半分または右半分、または 2 つに重なるセグメントに存在する必要があるため、左右に重なる最大の部分配列を見つけなければなりません。各ケースの最大サブ配列を比較すると、最大のものが戻り値になります。
そのタスクを適切に実行するコードを書いたと思いますが、その評価は間違っているようです。インストラクターと TA に助けを求めて連絡を取ろうとしてきましたが、どちらともうまくいっているようには感じません。以下は、これまでになんとか書いたコードです。明らかなエラーがあれば教えてください。繰り返しますが、明示的なコードや回答を探しているわけではありませんが、何が間違っているのかを理解するのに役立ちます。ここで紹介した同様のケースをすべて調べましたが、本当に役立つものは見つかりませんでした。また、ガイダンスを求めて Google 検索を何度も行いましたが、それもあまり役に立ちません。とにかく、問題のコードは次のとおりです。
int conquer(int arr[], int first, int mid, int last) {
int i = 0;
int maxLeft = 0;
int maxRight = 0;
int temp = 0;
for (i = mid; i >= first; i--) {
temp = temp + arr[i];
if (maxLeft < temp) {
maxLeft = temp;
}
}
temp = 0;
for (i = (mid + 1); i <= last; i++) {
temp = temp + arr[i];
if (maxRight < temp) {
maxRight = temp;
}
}
return (maxLeft + maxRight);
}
int divide(int arr[], int start, int end) {
int i;
int maxSum;
int maxLeftSum;
int maxRightSum;
int maxOverlapSum;
if (start == end) {
return arr[start];
} else {
int first = start;
int mid = (end / 2);
int last = end;
maxSum = 0;
maxLeftSum = 0;
for (i = first; i < mid; i++) {
maxSum = maxSum + arr[i];
if (maxLeftSum < maxSum) {
maxLeftSum = maxSum;
}
}
for (i = (mid + 1); i < last; i++) {
maxSum = maxSum + arr[i];
if (maxRightSum < maxSum) {
maxRightSum = maxSum;
}
}
maxOverlapSum = conquer(arr, first, mid, last);
}
if ((maxLeftSum > maxRightSum) && (maxLeftSum > maxOverlapSum)) {
return maxLeftSum;
} else if ((maxRightSum > maxLeftSum) && (maxRightSum > maxOverlapSum)) {
return maxRightSum;
} else
return maxOverlapSum;
}
編集:私が得ているエラーは間違った結果です。他の 2 つのアルゴリズム間で一貫した正しい結果が得られましたが、これは正しくありません。
編集＃2：これは私のコードの更新版で、少しスリムになり、いくつか修正しました。まだ正しく動作していませんが、もっと近くなるはずです...
#include <stdio.h>
#include <stdlib.h>
int numarr[] = {22, -27, 38, -34, 49, 40, 13, -44, -13, 28, 46, 7, -26, 42,
29, 0, -6, 35, 23, -37, 10, 12, -2, 18, -12, -49, -10, 37, -5, 17,
6, -11, -22, -17, -50, -40, 44, 14, -41, 19, -15, 45, -23, 48, -1,
-39, -46, 15, 3, -32, -29, -48, -19, 27, -33, -8, 11, 21, -43, 24,
5, 34, -36, -9, 16, -31, -7, -24, -47, -14, -16, -18, 39, -30, 33,
-45, -38, 41, -3, 4, -25, 20, -35, 32, 26, 47, 2, -4, 8, 9, 31, -28,
36, 1, -21, 30, 43, 25, -20, -42};
int length = ((sizeof(numarr))/(sizeof(int)));
int divide(int left, int right) {
int mid, i, temp, mLeft, mRight, mCross = 0;
if (left == right) {
return left;
} else if (left > right) {
return 0;
} else {
mid = (left + right) / 2;
divide(left, mid);
divide(mid + 1, right);
for (i = mid; i >= left; i--) {
temp = temp + numarr[i];
if (mLeft < temp) {
mLeft = temp;
}
}
for (i = mid + 1; i <= right; i++) {
temp = temp + numarr[i];
if (mRight < temp) {
mRight = temp;
}
}
mCross = (mLeft + mRight);
printf("mLeft: %d\n", mLeft);
printf("mRight: %d\n", mRight);
printf("mCross: %d\n", mCross);
return 0;
}
}
int main(int argc, char const *argv[])
{
divide(0, length);
return 0;
}