The maximum-subarray problem

write a program to find the nonempty, contiguous subarray of an Array whose values have the largest sum.This contiguous subarray is called the maximum subarray.
/*
 * Brute Force
 */
int * FindMaxSubArray0(int A[], int n)
{
    int i,j,sum,high,low;
    int *max = (int *)malloc(n*sizeof(int));
    int *end_pos = (int *)malloc(n*sizeof(int));
    int *p = (int *) malloc(3* sizeof(int));
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
          sum = max[i];
          for(j = i+1; j < n; j++) {
                sum = sum + A[j];
                if(sum > max[i]) {
                        max[i] = sum;
                        end_pos[i] = j;
                }
          }
    }
    p[0] = 0;
    p[1] = end_pos[0];
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                  p[2] = max[i];
                  p[0] = i;
                  p[1] = end_pos[i];
          }
    }
    return p;
}
/*
 * Divide-and-Conquer strategy
 */
int * FindMaxCrossSubArray(int A[],int low,int high,int mid)
{
     int i,sumleft = A[mid],sumright = A[mid+1], sum,left,right;
     int *p =(int *)malloc(sizeof(int) * 3);
     sum = sumleft;
     left = mid;
     for(i = mid-1; i > low; i--) {
           sum = sum+ A[i];
           if(sum > sumleft) {
                   sumleft = sum;
                   left = i;
           }
     }
     sum=sumright;
     right = mid+1;
     for(i = mid+2; i < high; i++) {
           sum = sum + A[i];
           if(sum > sumright) {
                   sumright = sum;
                   right = i;
           }
     }
     p[0] = left;
     p[1] = right;
     p[2] = sumleft+sumright;
     return p;
}
int * FindMaxSubArray1(int A[], int low, int high)
{
     int mid, *left=NULL, *right=NULL, *cross=NULL, *p = NULL;
     if(low == high) {
            p =(int *)malloc(sizeof(int) * 3);
            p[0] = p[1] = low;
            p[2] = A[low];
            return p;
     } else {
            mid = (low+high)/2;
            left = FindMaxSubArray1(A,low,mid);
            right = FindMaxSubArray1(A,mid+1,high);
            cross = FindMaxCrossSubArray(A,low,high,mid);
            if(left[2] >= right[2] && left[2] >= cross[2]) {
                       return left;
            } else if(right[2] >= left[2] && right[2] >= cross[2]) {
                   return right;
            } else {
                   return cross;
            }
     }
}
/*
 * Dynamic Programmming Methodology
 */
int * FindMaxSubArray2(int A[], int n)
{
    int *max, *end_pos, sum=0,*p,i;
    max = (int*) malloc(sizeof(int)*n);
    end_pos = (int*) malloc(sizeof(int)*n);
    p = (int*) malloc(sizeof(int)*3);
    for(i = 0; i < n; i++) {
          max[i] = A[i];
          end_pos[i] = i;
    }
    for(i = 1; i < n; i++) {
          sum = max[i-1] + max[i];
          if(sum > max[i]) {
                  max[i] = sum;
                  end_pos[i] = i;
          }
    }
    p[2] = max[0];
    for(i = 1; i < n; i++) {
          if(max[i] > p[2]) {
                    p[2] = max[i];
                    p[1] = i;
          }
    }
    for(i = p[1]; i > 0; i--) {
          if(end_pos[i] == i) {
                        p[0] = i;
                        break;
          }
    }
}