Complexidade de algoritmo

Relatório
MATEMÁTICA DISCRETA

Bruno Alves | Rui Freitas | José Gomes

Enunciado:
Pretende-se controlar o tráfego de alunos no ISEP. Em particular, quer-se saber qual o intervalo de tempo em que o acréscimo de alunos nas instalações do ISEP é máximo, e qual é esse acréscimo.
De modo a resolver este problema, é efetuado um controlo do número de alunos que entram/saem durante um certo período de tempo. A cada 5 minutos, é recolhida a informação N, que corresponde à diferença entre o número de alunos que entraram e saíram das instalações durante os últimos 5 minutos. Como exemplo, seja a sequência seguinte o resultado da medição durante 1 hora: [29, -32, -9, -25, 44, 12, -61, 51, -9, 44, 74, 4]

O problema de determinar qual o acréscimo máximo de alunos no ISEP, durante essa hora, consiste agora em determinar qual a subsequência contígua, da sequência anterior, cuja soma das suas entradas é máxima. Neste caso, a resposta seria a subsequência
[51, -9, 44, 74, 4] com soma igual a 164. Isto significa que, ao final deste período de 25 minutos, o ISEP tinha mais 164 alunos nas suas instalações.
Este problema motiva o que se enuncia em seguida, sendo o ponto de partida para o trabalho que se propõe:
Dada uma sequência de inteiros, encontre uma subsequência contígua cuja soma dos seus valores é máxima.
Façamos ainda a seguinte consideração. Uma subsequência vazia é considerada como tendo a soma 0. Assim, se todos os elementos da sequência inicial são negativos, o resultado deve ser a subsequência vazia.

Questão 1:
E: Construa um algoritmo que resolve o problema do enunciado e que consiste numa solução de força bruta, ou seja, o algoritmo deve examinar todas as subsequências contíguas da sequência inicial e devolver o seguinte: unia subsequência com soma máxima e o valor da sua soma. No relatório, apresente o algoritmo em pseudocódigo.

R:

function MaxSubSeq(seq): int size = seq.length() lista tmp lista maior int soma,