<file_sep>/*
Find Max Subarray by Enumeration
Loop over each pair of indices
i, j and compute the sum,
Sigma(f)(k=i) a[k] 
Keep the best sum you have found so far
*/

#include <stdio.h>

/*
Pre: a[] is an array of integers of length n
Post: a[] is now the max subarray
Returns: int which represents greatest sum in 
	subarray
*/


int enumMaxSubarray(int a[], int n){
	

	//counters
	int i; //pos of first term in subarray 
	int j; //last term in subarray
	int k; //current term in subarray

	//int currentArray [n];
	int currentArrayLength;
	//int maxArray [n];
	int maxArrayLength;
	int sum = 0;
	int best = 0;

	for (i = 0; i < n; i++) //first term
	{
		for (j = i; j < n; j++){//last term
			sum = 0;//
			//eraseArray(currentArray);
			currentArrayLength = 0;
			for(k = i; k <= j; k++) //step thru terms
			{
				sum += a[k];
				//currentArray[(k-i)] = a[k];
				currentArrayLength++;
			}
				if (sum > best){
				best = sum; //new record
				maxArrayLength = currentArrayLength;
				//copyArray(currentrrentArray, maxArray, maxArrayLength);
			}
		} 
	}
	return best;
}
<file_sep>
TODO

Algorithms

- enumeration
- [x] enumeration (a1.c) returns correct sum 
- [x] a1.c returns correct sum for test file

- better enum
- [x] a2.c returns correct sum    
- [x] a2.c tested with test file

- div and conq 
- [x] a3.c seems to return correct sum
- [x] a3.c tested with test file


Analysis
- [x] a1.c analysis data collected
- [x] a2.c analysis data collected
- [x] a3.c analysis data collected

Report
- Mathematical analysis
- 
-  pseudocode
- [x] a1 pseudocode
- [x] a2 pseudocode
- [x] a3 pseudocode
- [x] asymptomatic run times

- Theoretical correctness
- [ ] a3 proof

- Testing
- [x] results of testing against document 

- Experimental analysis
- [x] plots 
- [ ] what else?

- Extrapolation and interpretation
- [x] biggest size arrays solvable in an hour
- [ ] experimental results vs theoretical
<file_sep>/*


Finding the maximum sub-array
Divide and Conquer

If we split the array into two halves, we know that the maximum
subarray will either be
• contained entirely i n the first half,
•contained entirely in the second half, or
•made of a suffix of the first half of maximum sum and a prefix of the second half of maximum sum

The first two cases can be found recursively. The last case can be found in linear time
*/


#include <stdio.h>
#include <stdlib.h>
#include <math.h> //fmax

int divAndConMaxSubarray(int a[], int lo, int hi)
{
	//int* sumArray = malloc((hi - lo) * sizeof(int)); //for storing winning array, 
		//maybe don't need
	
	//midpoint of array
	int midpoint;
	
	//max's found w/ div and conq
	int leftMax=0;
	int rightMax=0;

	//max's found crossing middle iteratively
	int bothMax=0;
	int bothMaxLeft=0;
	int bothMaxRight=0;

	//counters
	int i, sum;

	//base case, only 1 element in array
	//TODO: ensure no issue w/ no elements
	if (lo==hi) { //lo and hi are the same element
		return a[hi]; //sum is this element alone
	}

	//divide  array into two halves
	midpoint = (lo + hi)/2;

	//maximum of 

		//maximum sum on left
		//recursive call

	
	leftMax = divAndConMaxSubarray(a, lo, midpoint);

		//max sum on right
		//recursive call
	
	rightMax = divAndConMaxSubarray(a, midpoint+1, hi);

		//max sum from midpoint
			//find max going left

	bothMaxLeft = 0;
	sum = 0;
	for (i = midpoint-1; i >=0; i-- ){
		sum += a[i];
		if (sum > bothMaxLeft)
			bothMaxLeft = sum;
	}
	
			//find max going right
	bothMaxRight = 0;
	sum = 0;
	for (i = midpoint; i < hi; i++ ){
		sum += a[i];
		if (sum > bothMaxRight)
			bothMaxRight = sum;
	}
			//combine
	bothMax = bothMaxRight + bothMaxLeft;

	return fmax(bothMax, fmax(leftMax, rightMax));
}
<file_sep>/*

Algorithm 2: Better Enumeration
Notice that in the previous algorithm, 
the same sum is computed many
times. In particular, notice that Sigma(j)(k=i)a[k] 
can be computed from
Sigma(j-1)(k=1)a[k] in O(1) time, rather than
starting from scratch. Write a new version 
of the first algorithm that takes advantage 
of this observation
*/

#include <stdio.h>

int betterEnumMaxSubarray(int a[], int n){

	//counters
	int i, j; //1st term, curr term
	//don't need last term, go to the end every run
	
	//variables to store arrays
	/* array variables here */

	//sum variables
	int sum = 0;
	int best = 0;

	for (i = 0; i < n; i++){
		sum = 0; //new starting term, new sum
		for (j = i; j < n; j++){
			sum += a[j];
			if (sum > best){
				best = sum; //new winner

				/*
				TODO copy array segment here maybe
				*/
			}
		}
	}
	return best;
}
<file_sep>//tester.c

#include "a1.c"
#include "a2.c"
#include "a3.c"

#include <time.h>

int main(){
	clock_t start, end;
	double clockTime;
	int numElements[] = {100, 200, 300, 400, 500, 
						600, 700, 800, 900,
						1000, 2000, 3000, 4000, 5000,
						6000, 7000, 8000, 9000};
	int elementArray[9000];
	int i;
	int sum;
	srand ( time(NULL) );


	//loop to populate elementArray
	for (i=0; i < 9000; i++){
		elementArray[i] = (rand() % 100)-50;
	}
	
	//testing enumeration
	printf("enumeration\n");
	printf("elements\ttime\tsum\n");
	for (i = 0; i < 9; i++){
		start = clock();
		sum = enumMaxSubarray(elementArray, numElements[i]);
		end = clock();
		clockTime = ((double) (end - start))/CLOCKS_PER_SEC;
		printf("%d\t%f\t%d\n",numElements[i], clockTime, sum );
	}

	//testing better enumeration
	printf("\n\nbetter enumeration\n");
	printf("elements\ttime\tsum\n");
	for (i = 0; i < 18; i++){
		start = clock();
		sum = betterEnumMaxSubarray(elementArray, numElements[i]);
		end = clock();
		clockTime = ((double) (end - start))/CLOCKS_PER_SEC;
		printf("%d\t%f\t%d\n",numElements[i], clockTime, sum );
	}
	//testing divide and conquer
	printf("\n\ndivide and conquer\n");
	printf("elements\ttime\tsum\n");
	for (i = 0; i < 18; i++){
		start = clock();
		sum = divAndConMaxSubarray(elementArray,0, numElements[i]);
		end = clock();
		clockTime = ((double) (end - start))/CLOCKS_PER_SEC;
		printf("%d\t%f\t%d\n",numElements[i], clockTime, sum );
	}

/* stuff goes here */
	/* old shit
	int testArray[] = {-18, -47, -40, -43, -2, 48, 31, -24, 36, -49, 4, -29, -4, -39, 12, 24, 8, 40, 45, -17, 6, -11, -5, -30, -8, 25, -44, -9, -20, -50, -12, -32, 41, 10, -42, -15, 11, -38, 37, 21, 33, -22, 16, -41, -46, -33, -26, 7, -3, -28, 29, 20, 27, 3, 15, 49, 23, -1, 14, 32, -31, -13, -48, -14, 13, 39, 46, -35, -36, 0, 17, -27, -21, 28, -7, 44, -10, 34, -19, 47, 42, -34, 5, 26, -45, 35, 9, -25, 38, -37, -23, 22, -6, -16, 18, 43, 30, 2, 19, 1};
	int length = 100;
	int sum = 0;
	sum = divAndConMaxSubarray(testArray, 0, length);


	end = clock();

	clockTime = ((double) (end - start))/CLOCKS_PER_SEC;

	printf("sum = %d\n",sum);
	printf("clock time %d", clockTime);
*/ 
	
	//
	//loop to create giant array







	return 0;
}