/**************************************************************************

numseq.c

A program to solve and test the problem:
Given an array of integers, find the sequence of elements in that array
that will give the largest sum.

Compiled and tested with gcc under the redhat 5.1 distribution of Linux.

***************************************************************************/
#include <stdio.h>

#define	FALSE		(0)
#define TRUE		(!FALSE)

typedef struct seqstruct
  {
  int	*seqary;	// array of integers
  int	 seqst;		// index of start of maximum sequence
  int	 seqend;	// size of array on input, end of max sequence on output.
  int	 seqsum;	// sum of maximum sequence
  } seqstruct;


/*@begin_fn_hdr@=========================================================
 Name:		numseq
 Synopsis:	find the sequence of ints in an array that gives the largest sum
 Input:		seqstruct  *seqinfo;	// pointer to array and info
 		  seqinfo->seqary;	// pointer to array
 	          seqinfo->seqst;	// ignored on entry, return start of best sequence
		  seqinfo->seqend;	// size of array on entry, return end of best
		  seqinfo->seqsum;	// sum of best sequence

 Output:	return 0 for success, nonzero for failure.
 		modify the value of the seqinfo input parameter to return values.

 Description:
 Do in one pass through the array.	
 While the sign of the array elements does not change, 
   keep collecting the sum for that sign.
 When the sign changes, 
   if we are not in the middle of an ongoing sequence, 
     if the old sign was negative
       note the index of the first positive number as a possible new sequence start.
     if the old sign was positive
       if it is worth bridging the sequence of negative numbers
			       // is the sum of negative numbers smaller than both the old sum
			       // and the next sequence of positive numbers?
         add the sum of the collections of the following neg and pos sequences and continue
       else
         if the sum is better than the best sum so far
	   note the details of the sum
	 continue looking for a better sum.

 Testing:	The test sequences should include:
 		  0's, 
		  0, pos and neg at start
		  singles and multiples of negative and positive numbers, 
		  negatives that are both bigger and smaller than each or 
		  both of the surrounding positive sequences.
		  Only negative numbers (will need to find the best single number)
		  Only positvie numbers
		  All zeros
 Warnings:	Modifying struct passed to it.
 		Mostly inline code, efficient running, uses memory.
		currend may be superfluous

 Updates:	10/13/98 LRC	original
===========================================================@end_fn_hdr@*/


int numseq (seqstruct *seqinfo)
{

int		*val;				// array of values to find best sequence in
int		size;				// size of array
int		currst;				// start of current sequence being tested
int		currend;			// end of current sequence being tested
int		dbend;				// don't bridge end
int		currsum;			// sum of current sequence being tested
int		possum;				// sum of positive bridge test sequence
int		negsum;				// sum of negative bridge test sequence
int		idx;				// index of array element
int		tmp;				// temporary variable

						// flags
int		currpos;			// is the current val/sequence positive
int		lastpos;			// was the last val/sequence positive
int		onlyneg;			// have we only had negative numbers so far
int		seqinprog;			// Is a sequence worth testing in progress
int		bridge;				// Is it worth bridging a seq of neg numbers

val             = seqinfo->seqary;
size            = seqinfo->seqend;
						// Test input values
if (size <=0)					// if it's an illegal size
  return -1;					// return an error

  						// Initialize
seqinfo->seqst  = currst  = 0;			// initial start of best seq
seqinfo->seqend = currend = 0;			// initial end of best seq
seqinfo->seqsum = currsum = *val;		// this will be a sum
currpos         = *val >= 0;			// is the start of the array positive; 
onlyneg         = !currpos;			// have we only had negative numbers so far
seqinprog       =  currpos;			// only start a sequence with positive num

for (val++, idx = 1; idx < size; idx++, val++)	// test every element
  {
  lastpos = currpos;				// was the last number (seq) positive?
   					
  if (onlyneg && (*val > seqinfo->seqsum))	// If we've only had negative numbers. 
    {						// Best yet of single numbers.       
    seqinfo->seqst  = currst  = idx;
    seqinfo->seqend = currend = idx;
    seqinfo->seqsum = currsum = *val;
    onlyneg &= (*val >= 0);			// may have gone positive
    }

  if (! (*val))					// if current element == 0
    continue;					// no change, look at next number

  currpos = (*val > 0);
  if ((currpos != lastpos))			// sign change, end of gathering
    {
    if (!seqinprog) 		
      {
      if (currpos)				// just went pos, start a new sequence		         
        {					
        currst    = idx; 
        currend   = idx; 
        currsum   = *val;
        seqinprog = TRUE;
        }
      continue;					// not at end of sequence, look at next num
      }
 
    						///////////////////////////////
    						//
    						// End of sequence
    						//
    						///////////////////////////////
 
    if (!currpos)				// if goes neg, see if we need to bridge
      {
      bridge = TRUE;				// Assume that we will
      dbend  = idx - 1;				// end if we don't bridge
 
      while ((bridge == TRUE) && (idx < size))
        {
						// While there are still numbers in array
    						// check couplets of pos and neg seqs
 
         negsum = 0;				// gather neg nums and 0's
         for ( ;((idx < size) && (*val <= 0)); idx++, val++)
           {
           negsum += *val;
           }
 
         possum = 0;				// gather pos nums and 0's
        if (idx < size)
          {
           for ( ;((idx < size) && (*val >= 0)); idx++, val++)
             {
             possum += *val;
             }
          }
 
        tmp = (negsum + possum);
        if ((tmp > 0) && (currsum + negsum > 0))	// bridge this couplet?
          {
          currsum += tmp;			// yes
	  currend  = idx -1;
          }
        else
          {
	  currend   = dbend;
          bridge    = FALSE;			// no longer beneficial to bridge
          seqinprog = FALSE;
          }
        }					// end while
      }						// end if(!currpos)
 
    if (currsum > seqinfo->seqsum)		// Do we have the best seq so far?
      {
      seqinfo->seqst  = currst;
      seqinfo->seqend = currend;
      seqinfo->seqsum = currsum;
      }
    }						// end sign change					
  else 						// no sign change, continue with sum
    {
    currsum += *val;
    currend = idx;
    continue;
    }
  }						// end for each value in array
  if (currsum > seqinfo->seqsum)		// Do we have the best seq so far?
    {
    seqinfo->seqst  = currst;
    seqinfo->seqend = currend;
    seqinfo->seqsum = currsum;
    }
  return 0;
}						// end numseq()

/*@begin_fn_hdr@=========================================================
 Name:		main
 Synopsis:	test numseq function
 Input:		none
 Output:	print output of testcases
 Description:	call numseq with various testcases
 Testing:	
 Warnings:	Could also call each test case with any substring
 		first value of test case is number of entries	
 Updates:	10/13/98 LRC	original
===========================================================@end_fn_hdr@*/

void main (void)
{
int		tc0[]= {0};
int		tc1[]= {2, 1, 0};
int		tc2[]= {2, 1, -1};
int		tc3[]= {2, 1, 1};
		      	//	    80, -83,          23,        -12,     36 
int		tc4[]= {13, 12, 23, 45, -83, 2, 4, 5, 12, -2, -7, -3, 17, 19};
		      	// 		   -74,     60, -6  5
int		tc5[]= {9,-23, -14, -30, 0, -7, 23, 37, -6, 5};
int		tc6[]= {5, 0, 0, 0, 0, 0};
		      	//	       15
int		tc7[]= {-5, 1, 2, 3, 4, 5};
			//
int		tc8[]= {3, -23, -14, -30};
			//  1  -1     4          -9          16  -5
int		tc9[]= {12, 1, -1, 2, 2, -3, -3, -3, 4, 4, 4, 4, -5};
int		tc10[]={5, 12, -2, 1, -2, 12};
int	        *testcases[] = {tc0, tc1, tc2, tc3, tc4, tc5, tc6, tc7, tc8, tc9, tc10 };

int		tcnum;
int		tcidx;
int		tcsize;
int 		err;

int		*testseq;
seqstruct	tstruct;

for (tcnum = 0; tcnum < ((sizeof(testcases))/(sizeof(int *))); tcnum++)
  {
  tstruct.seqary = &(testcases[tcnum][1]);
  tstruct.seqend = tcsize = testcases[tcnum][0];
  printf("Test sequence %03d:\n", tcnum);
  printf("%03d elements.  ", tcsize);
  if (tcsize > 0)
    {
    for (tcidx = 1; tcidx <= tcsize; tcidx++)
      {
      printf("%03d, ", testcases[tcnum][tcidx]);
      if (!(tcidx%20))
        {
	printf("\n");
	}
      }						// end for each elem in testcase
    }
  printf("\n");
  err = numseq(&tstruct);
  if (err)
    {
    printf("Invalid.\n");
    }
  else
    {
    printf("Best sequence starts at %03d, ends at %03d, and has the sum %03d\n",
    	    tstruct.seqst, tstruct.seqend, tstruct.seqsum);
    }
  }						// end for each testcase


}