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

Dynamic Programming(DP)

Introduction

A DP is an algorithmic technique which is usually based on a recurrent formula and one (or some) starting states.DP applies when the subproblems overlap - that is, when subproblems share subsubproblems.

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

• Characterize the structure of an optimal solution.
• Recursively define the value of an optimal solution.
• Compute the value of an optimal solution, typically in a bottom-up fashion.
• Construct an optimal solution from computed information.

Refer wiki link for more information
http://en.wikipedia.org/wiki/Dynamic_programming