My linear algorithm for maximum subarray problem

I can proudly say I developed this algorithm.  But I certainly need to look at the hint of Programming Pearl Chapter 8 as well as the hint at 4-1.5.  Though, make it working myself still makes me feel happy.

It is arguable that the algorithm could be too long so I might want to read other on-line references. 

Should this be part of practice routine?  It sounds like so.  Though, it is more thought-provoking to finish exercises at the end of Programming Pearl Chapter 8.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define N 100
#define M 100000

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

int main(int c, char* v[])
{
  int A[N];
  int i,k;

  struct arr_struct max_array, max_suffix_array;

  for(k=0;k<M;k++){
    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");
   
    max_array.s = A[0];
    max_array.b = 0;
    max_array.e = 0;
   
    max_suffix_array.s = A[0];
    max_suffix_array.b = 0;
    max_suffix_array.e = 0;
   
    for(i=1;i<N;i++){
      if(max_suffix_array.s>0)
        max_suffix_array.s+=A[i];
      else{
        max_suffix_array.s=A[i];
        max_suffix_array.b=i;
      }
      max_suffix_array.e=i;
     
      if(max_array.s < max_suffix_array.s){
        max_array.s = max_suffix_array.s;
        max_array.b = max_suffix_array.b;
        max_array.e = max_suffix_array.e;
      }
    }

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

Status 20110620

Finished the brute force implementation.  Of course it is nothing difficult.  This is a place I want to stay on a while because the 3 algorithms of finding maximum subarray are quite illuminating.

Fuzzy reading: 414/1144
Browse reading: 309/1144
Exercises up to 4-1.3(finished the brute force implementation)

Needs write up: P2.1c, 3-2.4, 3-2.8, P3.1

Exercises which are finished but not on paper: 1.1-2, 1.2-2, 1.2-3, P1-1, 4.1-5, 4.2-6, 4.2-7, 4.3-{1,2,4,5,6}, The whole Section 4.4, 4.5-1, P4.4(a-c), P4.6b, 5.1-{1,2}, whole Section 6.1, 6.2-{1,2,4,5,6}, 6.3-1, whole Section 7.1, 7.2-{1-3}, whole Section 7.3 and 7.4.3, 10.1-6, 10.1-7, 12.1-{1,2,4} 12.2-{2.3}, 12.4-4, P12.4(a), 15-1.1, 15.1-3, 15.3-3, 15.5, A.1-{1,2,3,4,5,7},  C.1-{2,4,5,7,8,9,14}, C.2-{1,2,4,5}, C.3-{1,2,10}, all in D.1. and D.2-2

Maximum subarray brute force algorithm (quadratic time) 1

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

int main(int c, char* v[])
{
  int A[N];
  int i,j;
  int b, e;
  int sum, max_sum;
  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");

  b=-1;
  e=-1;
  max_sum=-INT_MAX;
  for(j=0;j<N;j++){
    sum=0;
    for(i=j;i<N;i++){
      sum+=A[i];
      if(sum>max_sum){
        max_sum=sum;
        b=j;
        e=i;
      }
    }
  }
  printf("max_sum %d b %d e %d\n",max_sum, b, e);
  return 0;
}