2191-saldo-de-gols

# yaml-language-server: $schema=https://api.mundodocodigo.com.br/api/public/json/wok-problem.json --- version: "0.5" id: 2191 name: "Saldo de Gols" slug: "saldo-de-gols" timelimit: 1.0 memlimit: 200 difficultyLevelId: C author: "SBC" origin: "Beecrowd" description: 'Encontre o período de partidas em que o time teve o maior saldo de gols usando o Algoritmo de Kadane (Soma Máxima de Subvetor).' editorial: | Este problema pede que encontremos a subsequência contígua com a maior soma (saldo de gols). Uma solução O(N^2) ou O(N^3) usando laços aninhados causaria *Time Limit Exceeded* (TLE) para as 10000 partidas, sendo exigido um algoritmo mais eficiente. A solução perfeita é usar o Algoritmo de Kadane, que varre o vetor uma única vez (Complexidade O(N)). Toda vez que o saldo acumulado (`current_sum`) for negativo, significa que a sequência atual só pioraria qualquer resultado futuro. Portanto, o acumulador é zerado e o marcador de início é atualizado para o próximo elemento. Caso contrário, comparamos com a soma máxima global (`max_sum`) e atualizamos a melhor resposta. Atenção ao critério de desempate do problema: se a soma empatar com a máxima, deve-se escolher o período mais longo (`end - start > best_end - best_start`). successmsg: 'Parabéns! Dominar o algoritmo de Kadane é um salto gigante na sua capacidade de otimizar problemas de subsequência de $O(N^2)$ para $O(N)$!' timeComplexity: O(N) skills: - max-subarray - arrays statements: - id: a-saldo testScenarioLevel: A thematicSkills: - skill: max-subarray points: 2 testScenarios: - id: a-performance name: Carga N Alta description: "Várias instâncias com N=10000." helpTip: "Seu programa varre o array com 1 ou 2 loops aninhados? Um algoritmo N^2 vai estourar o limite. Use Kadane." level: A testType: PERFORMANCE skills: - skill: max-subarray points: 1 - id: b-fuzzing name: Empates Variados description: "Sequências onde vários períodos possuem o mesmo saldo." helpTip: "Você programou o critério de desempate corretamente escolhendo o maior tamanho (J - I)?" level: B testType: TDD skills: - skill: max-subarray points: 1 - id: c-edge name: Sem Saldo Positivo description: "Time só perdeu ou empatou. Saldo <= 0." helpTip: "Você lembrou de imprimir 'nenhum' quando o max_sum é 0 ou negativo?" level: C testType: TDD skills: - skill: ad-hoc points: 1 - id: d-sample name: Exemplo do Enunciado description: "Casos de teste do problema original." helpTip: "Passe o caso de teste." level: D testType: TDD skills: - skill: basic-io points: 1 solutions: - id: a-otima-basica name: Algoritmo de Kadane description: Varre acumulando saldos e recomeça a subsequência quando negativa em O(N). level: A implementations: - language: cpp paradigm: Imperative main: saldo.cpp filenames: - saldo.cpp - language: py paradigm: Imperative main: saldo.py filenames: - saldo.py - language: java paradigm: OO main: Saldo filenames: - Saldo.java authorSlugProblem: Unknown defaultStatement: a-saldo