Solução por Lucca Siaudzionis
Este é um problema conhecido de algoritmos gulosos. Imagine que, em vez de o array que representa a pizza ser cíclico, ele seja linear. Ou seja, temos um array de vários número inteiros e queremos o sub-array de maior soma. Neste caso, mantemos uma variável soma, inicialmente zerada, e percorremos o array, sempre acrescentando o valor da casa que estamos a variável soma. Quando tivermos 
, resetamos soma para 
.
Agora, para transformamos esta solução para resolver o problema Pizza, temos que fazer duas alterações:
- duplicar nosso array ("copiando" o mesmo array ao lado do original)
- além de checar se , também precisamos checar se já não acrescentamos mais que
valores a variável soma.
O código, então, fica assim:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // pizza.cpp | |
| // programas2 | |
| // | |
| // Created by Lucca Siaudzionis on 03/01/13. | |
| // Copyright (c) 2013 Luccasiau. All rights reserved. | |
| // | |
| #include <cstdio> | |
| #include <cstdlib> | |
| #include <cstring> | |
| #define max(A,B) (A)>(B)?(A):(B) | |
| #define MAXN 200010 | |
| int main(){ | |
| int n; | |
| int myv[MAXN]; | |
| memset(myv,0,sizeof myv); | |
| scanf("%d",&n); | |
| for(int i = 1;i<=n;i++){ | |
| scanf("%d",&myv[i]); | |
| myv[n+i] = myv[i]; | |
| } | |
| int cont = 0; | |
| int soma = 0; | |
| int resp = 0; | |
| for(int i = 1;i<=2*n;i++){ | |
| soma += myv[i]; | |
| resp = max(resp,soma); | |
| cont++; | |
| //printf("(%d %d)\n",soma,resp); | |
| if(soma < 0){ | |
| soma = 0; | |
| cont = 0; | |
| //printf("[%d]\n",i); | |
| } | |
| if(cont == n){ | |
| cont = 0; | |
| soma = 0; | |
| i = i-n+2; | |
| } | |
| } | |
| printf("%d\n",resp); | |
| return 0; | |
| } |