#include <stdio.h>



/* Optimal, slow version O(n^3) */
int MaxSubSlow( int *v, int nv ) {
	
	int i,j, maxi,maxj, maxval, k;

	maxval = v[0];
	maxi = 0;
	maxj = 0;


	for (i=0; i < nv; i++) {
		for (j=i; j < nv; j++) {
			int sum =0;

			for (k=i; k<=j; k++) {
				sum += v[k];
			}

			if (sum > maxval) {
				maxval = sum;
				maxi = i;
				maxj = j;
			}
			
		}
	}
	printf( "[%d %d]\n", maxi, maxj );
	return maxval;
}


/* Optimal, dynamic programming */
int MaxSubFast( int *v, int nv ) {
	int A[nv];      /* Max value */
	int START[nv];  /* Start of interval */
	int i;

	/* Init the arrays, just for good practice */
	for (i=0; i < nv; i++){
		A[i] = -1;
		START[i] = -1;
	}
	
	A[0] = v[0];
	START[0] = 0;

	for (i = 1; i < nv; i++) {

		int tmp;

		tmp = A[i-1] + v[i];
		if (v[i] > tmp)  {
			A[i] = v[i];
			START[i] = i;
		} else {
			A[i] = tmp;
			START[i] = START[i-1];
		}
	}

	int max = A[0], maxend= 0;

	for (i=1; i < nv; i++)
		if (A[i] > max) {
			max = A[i];
			maxend =i; 
		}
	printf( "[%d %d]\n", START[maxend], maxend );
	return max;
}

int main( void ) {
	int v[] = {1,2,4,2,-490,-2,1,2,-34,-2, 5, -1909};
	int nv = 12;

	printf( "Slow -> %d\n", MaxSubSlow( v, nv ) );
	printf( "Fast -> %d\n", MaxSubFast( v, nv ) );

}