/*------------------------------------------------------------------------------
 * subarray.c: maximal subarray
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>

#include <limits.h>

/*------------------------------------------------------------------------------
 * Constants 
**----------------------------------------------------------------------------*/

#define NMAX_INTS   100
#define MAX_STRLEN  1024

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

inline int
compute_sum(int a[], int s, int e)
{
    int i, sum = 0;

    for (i = s; i <= e; i++)
	sum += a[i];

    return (sum);
}

/*----------------------------------------------------------------------------*/

static int
find_maximal_subarray_brute_force(int a[], int n, int *s, int*e)
{
    int i, j, cur_sum, max_sum = INT_MIN;

    for (i = 0; i < n; i++) {
	for (j = 0; j < n; j++) {
	    cur_sum = compute_sum(a, i, j);
	    if (cur_sum > max_sum) {
		max_sum = cur_sum;
		*s = i;
		*e = j;
	    }
	}
    }

    return (max_sum);
}

/*----------------------------------------------------------------------------*/

static int
find_maximal_subarray_dynamic(int a[], int n, int *s, int*e)
{
    int i, j = 0, cur_sum = 0, max_sum = INT_MIN;

    *s = *e = 0;
    for (i = 0; i < n; i++) {
	cur_sum = cur_sum + a[i];
	if (cur_sum > max_sum) {
	    max_sum = cur_sum;
	    *s = j;
	    *e = i;
	}
	if (cur_sum < 0) {
	    cur_sum = 0;
	    j = i + 1;
	}
    }

    return (max_sum);
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    char  b[MAX_STRLEN];
    char *tp;
    int   a[NMAX_INTS];
    int   s, e, i, n;

    while (fgets(b, MAX_STRLEN, stdin)) {
	tp = strtok(b, " ");
	for (n = 0; tp; n++) {
	    sscanf(tp, "%d", &a[n]);
	    tp = strtok(NULL, " ");
	}

	printf("%d:", find_maximal_subarray_brute_force(a, n, &s, &e));
	for (i = s; i <= e; i++)
	    printf(" %d", a[i]);
	putchar('\n');

	printf("%d:", find_maximal_subarray_dynamic(a, n, &s, &e));
	for (i = s; i <= e; i++)
	    printf(" %d", a[i]);
	putchar('\n');
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=c
**----------------------------------------------------------------------------*/