Voltar

## Subvetor de soma máxima - Paradigmas

0 Curtidas
```/*
* Largest subvector sum
*
* Author: Howard Cheng
* Reference: Programming Pearl, page 74
*
* Given an array of integers, we find the continguous subvector that
* gives the maximum sum.  If all entries are negative, it returns
* an empty vector with sum = 0.
*
* If we want the subvector to be nonempty, we should first scan for the
* largest element in the vector (1-element subvector) and combine the
* result in this routine.
*
* The sum is returned, as well as the start and the end position
* (inclusive).  If start > end, then the subvector is empty.
*
*/

#include
#include
#include

int vecsum(int *v, int n, int *start, int *end)
{
int maxval = 0;
int max_end = 0;
int max_end_start, max_end_end;
int i;

*start = max_end_start = 0;
*end = max_end_end = -1;
for (i = 0; i < n; i++) {
if (v[i] + max_end >= 0) {
max_end = v[i] + max_end;
max_end_end = i;
} else {
max_end_start = i+1;
max_end_end = -1;
max_end = 0;
}

if (maxval < max_end) {
*start = max_end_start;
*end = max_end_end;
maxval = max_end;
} else if (maxval == max_end) {
/* put whatever preferences we have for a tie */
/* eg. longest subvector, and then the one that starts the earliest */
if (max_end_end - max_end_start > *end - *start ||
(max_end_end - max_end_start == *end - *start &&
max_end_start < *start)) {
*start = max_end_start;
*end = max_end_end;
maxval = max_end;
}
}
}
return maxval;
}

int main(void)
{
int n;
int *v;
int i;
int sum, start, end;

while (scanf("%d", &n) == 1 && n > 0) {
v = (int *)malloc(n*sizeof(int));
assert(v);
for (i = 0; i < n; i++) {
scanf("%d", &(v[i]));
}
sum = vecsum(v, n, &start, &end);
printf("Maximum sum %d from %d to %d.\n", sum, start, end);
free(v);
}

return 0;
}
```