Shortcut for chapter specific information

Monday, June 20, 2011

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

No comments:

Post a Comment