Finished the recursive algorithm at 4-1.3!

I am quite cite.  It's cute program and it's not hard to understand once you know the algorithm.  Ok, I will do the measurement tomorrow.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 10000

struct arr_struct { int b;  int e;  int s; };

void find_max_crossing_subarray(int a[],int l, int m, int h, struct arr_struct* as_p)
{
  int left_sum = -INT_MAX;
  int sum =0 ;
  int max_left =-1;
  int max_right =-1;
  int i,j;
  for( i = m ; i >=l ; i--){
    sum += a[i];
    if(sum > left_sum){
      left_sum = sum;
      max_left = i;
    }
  }
  int right_sum = -INT_MAX;
  sum =0 ;
  for( j = m+1 ; j <=h ; j++){
    sum += a[j];
    if(sum > right_sum){
      right_sum = sum;
      max_right = j;
    }
  }
  as_p->b = max_left;
  as_p->e = max_right;
  as_p->s = left_sum + right_sum;
}
 

void find_maximum_subarray(int a[],int l, int h, struct arr_struct *as_p)
{
  if(h==l){
    as_p->b = l;
    as_p->e = h;
    as_p->s = a[l];
  }else{
    int m;
    struct arr_struct left, right, cross;
    m= l + (h-l)/2;
    find_maximum_subarray(a,l,m,&left);
    find_maximum_subarray(a,m+1,h,&right);
    find_max_crossing_subarray(a,l,m,h,&cross);

    if(left.s >= right.s && left.s >= cross.s){
      as_p->b = left.b;
      as_p->e = left.e;
      as_p->s = left.s;
    }else if(right.s >= left.s && right.s >= cross.s){
      as_p->b = right.b;
      as_p->e = right.e;
      as_p->s = right.s;
    }else{
      as_p->b = cross.b;
      as_p->e = cross.e;
      as_p->s = cross.s;
    }
  }
}


int main(int c, char* v[])
{
  int A[N];
  int i;
  struct arr_struct max_array;
  for(i=0;i<N;i++){
    A[i]= 1 + (int ) (N * (float)rand()/(float)RAND_MAX) - N/2 ;
    //    printf("%d:%d ",i,A[i]);
  }
  //  printf("\n");
  find_maximum_subarray(A,0,N-1,&max_array);

  printf("Begin %d\n",max_array.b);
  printf("End %d\n",max_array.e);
  printf("Sum %d\n",max_array.s);

  return 0;
}