Wednesday, May 22, 2013

Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized


#include<stdio.h>
#define MAX(a,b) ((a>b)?(a):(b))
main()
{
  int arr[]={-2, -3, 4, -1, -2, 1, 5, -3};
  int len,i;
  int max=0;
  len = sizeof(arr)/sizeof(arr[0]);
  max=arr[0];
  int finalmax=0;
  int start=0,end=0;
  for(i=1;i<len;i++)
  {
    max = MAX(max+arr[i], arr[i]); 
      
        finalmax=MAX(max,finalmax);
    
  }
 
    
      printf("MAX:%d %d %d \n",finalmax, start ,end);
 
   
   
}
Example if you want to print array http://codepad.org/BhYxSlp4

3 comments :

Avi Dullu said...

the MAX in the if condition is useless.

Unknown said...

@Avi , yeah thanks for informing , i missed to remove it , i have updated the post

Unknown said...
This comment has been removed by the author.