Piszę kod, aby znaleźć maksymalną sumę ciągłej pod-tablicy w C. Logika wydaje się według mnie w porządku, ale nadal nie jest poprawna. Zajrzyj do kodu. Algorytm dzieli większą tablicę na 2 pod macierze. Następnie sprawdza pod-tablicę maksymalnej sumy, badając lewą tablicę, prawą tablicę, a także tablicę zawierającą punkt środkowy (sprawdzi prawą i lewą stronę od punktu środkowego, a następnie zwróci podzakres sumy maksymalnej zawierający punkt środkowy).

int* cross_max(int arr[], int low, int mid, int high)
{
    int left_max, left_sum = -2000;
    int sum = 0;
    int i;
    for(i=mid; i>=low;i--)
    {
        sum = sum + arr[i];
        if(sum > left_sum)
        {
            left_sum = sum;
            left_max = i;
        }
    }


    int right_max, right_sum = -2000;

    for(i=mid+1; i<=high;i++)
    {
        sum = sum + arr[i];
        if(sum > right_sum)
        {
            right_sum = sum;
            right_max = i;
        }
    }

    // 0 - sum
    // indices - 1,2

    int temp_arr[3] = {0,0,0};
    temp_arr[0] = left_sum + right_sum;
    temp_arr[1] = left_max;
    temp_arr[2] = right_max;

    int *p = temp_arr;

    printf("\n Maximum sum = %d\n",*p);
    printf("\n low = %d\n",*(p+1));
    printf("\n high = %d\n",*(p+2));    

    return p;

}


int* find_max(int arr[], int low, int high)
{
    int temp_arr[3] = {0,0,0};
    if(low == high)
    {
        temp_arr[0] = arr[low];
        temp_arr[1] = low;
        temp_arr[2] = low;

        int *q = temp_arr;
        return q;
    }

    int mid = (low + high)/2; 

    int* a1 =  find_max(arr,low,mid);
    int* a2 =  find_max(arr,mid+1,high);
    int* a3 =  cross_max(arr,low,mid,high);

    if (*a1 > *a2 && *a1 > *a3)
        return a1;

    else if (*a2 > *a1 && *a2 > *a3)
        return a2;

    else
        return a3;

}


int main()
{
    int arr[8] = {1,1,2,-2,3,3,4,-4};

    int *point = find_max(arr,0,7);

    printf("\n Maximum sum = %d\n",*point);
    printf("\n low = %d\n",*(point+1));
    printf("\n high = %d\n",*(point+2));    
    return 0;
}