Maximum Subarray: Teile und herrsche

Disclaimer: dies ist für eine Zuordnung. Ich bin nicht zu Fragen, für die explizit programmiert werden, es müssen nur genug helfen zu verstehen, die der Algorithmus beteiligt, so dass ich vielleicht beheben Sie die Fehler in meinem code.

Okay, also du bist wahrscheinlich vertraut mit der maximum-subarray problem: Berechnung und Rückgabe der größte zusammenhängende block von ganzen zahlen in einem array. Einfach genug, aber diese Zuordnung verlangt von mir zu tun es in drei verschiedenen Komplexitäten: O(n^3), O(n^2) und O(n log n). Ich habe die ersten beiden ohne viel Mühe (brute force) aber die Dritte gibt mir Kopfschmerzen ... buchstäblich.

Ich verstehen, wie der Algorithmus funktionieren soll: ein array an eine Funktion übergeben, teilt es in zwei Hälften rekursiv, vergleicht dann die einzelnen Komponenten zu finden, die maximale subarray in jeder Hälfte. Dann, da die maximale subarray muss, befindet sich ganz in der linken oder rechten Hälfte, oder in einem segment überlappen die beiden, Sie müssen das maximale subarray, die überlappungen Links und rechts. Vergleichen Sie die max subarrays für jeden Fall, und die größte wird Ihren Wert zurückgeben.

Ich glaube, ich habe code geschrieben, der führt, der Aufgabe angemessen, aber ich scheine falsch zu sein in der Bewertung. Ich habe versucht, an den Lehrer und TA für die Hilfe, aber ich habe nicht das Gefühl, dass ich immer überall mit, entweder von Ihnen. Unten ist der code hab ich es geschafft zu schreiben so weit. Bitte sagen Sie mir, wenn Sie irgendwelche eklatante Fehler. Nochmal, ich bin nicht auf der Suche nach expliziten code oder Antworten, aber helfen, zu verstehen, was ich falsch mache. Ich habe gesucht durch alle ähnliche Fälle hier vorgestellt und habe nicht gefunden was kann mir wirklich helfen. Habe ich auch getan, viele der Google-Suche nach Orientierung, aber auch das hilft nicht viel, entweder. Wie auch immer, hier ist der code in Frage:

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;
}

Edit: die Fehler, die ich bin immer ein Falsches Ergebnis. Ich habe konsistente und korrekte Ergebnisse zwischen meine beiden anderen algorithmen, aber das ist falsch.

Edit #2: Hier ist eine aktualisierte version von meinem code abgespeckt ein bisschen und ich wurden ein paar Dinge. Es ist immer noch nicht korrekt läuft, sollte es doch viel näher...

#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;
}