시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 63 37 30 57.692%

문제

연종이는 창업했다. 오늘은 창업한지 N일이 되었고, 매일 매일 수익을 적어놓았다.

어느날 연종이는 가장 많이 돈을 번 구간이 언제인지 궁금해졌다.

오늘이 창업한지 6일 되었고, 수익이 다음과 같다고 하자.

  • 1일: -3
  • 2일: 4
  • 3일: 9
  • 4일: -2
  • 5일: -5
  • 6일: 8

이 때, 가장 많은 돈을 번 구간은 2~6까지이고 총 수입은 14이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N이 주어져 있다. (1 ≤ N ≤ 250,000) 둘째 줄부터 N개의 줄에는 매일 매일의 수익 P가 주어진다. (-10,000 ≤ P ≤ 10,000) 수익은 첫 날부터 순서대로 주어진다. 입력의 마지막 줄에는 0이 주어진다.

출력

각 테스트 케이스에 대해서 가장 많은 수익을 올린 구간의 수익을 출력한다. 단, 구간이 비어있으면 안된다.

예제 입력 1

6
-3
4
9
-2
-5
8
2
-1000
-19
0

예제 출력 1

14
-19
W3sicHJvYmxlbV9pZCI6IjQwOTciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMyMThcdWM3NzUiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzVmMFx1Yzg4NVx1Yzc3NFx1YjI5NCBcdWNjM2RcdWM1YzVcdWQ1ODhcdWIyZTQuIFx1YzYyNFx1YjI5OFx1Yzc0MCBcdWNjM2RcdWM1YzVcdWQ1NWNcdWM5YzAgTlx1Yzc3Y1x1Yzc3NCBcdWI0MThcdWM1YzhcdWFjZTAsIFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2MgXHVjMjE4XHVjNzc1XHVjNzQ0IFx1YzgwMVx1YzViNFx1YjE5M1x1YzU1OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNWI0XHViMjkwXHViMGEwIFx1YzVmMFx1Yzg4NVx1Yzc3NFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzc0IFx1YjNjOFx1Yzc0NCBcdWJjODggXHVhZDZjXHVhYzA0XHVjNzc0IFx1YzViOFx1YzgxY1x1Yzc3OFx1YzljMCBcdWFkODFcdWFlMDhcdWQ1NzRcdWM4NGNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzYyNFx1YjI5OFx1Yzc3NCBcdWNjM2RcdWM1YzVcdWQ1NWNcdWM5YzAgNlx1Yzc3YyBcdWI0MThcdWM1YzhcdWFjZTAsIFx1YzIxOFx1Yzc3NVx1Yzc3NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0XHVhY2UwIFx1ZDU1OFx1Yzc5MC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xXHVjNzdjOiAtMzxcL2xpPlxyXG5cdDxsaT4yXHVjNzdjOiA0PFwvbGk+XHJcblx0PGxpPjNcdWM3N2M6IDk8XC9saT5cclxuXHQ8bGk+NFx1Yzc3YzogLTI8XC9saT5cclxuXHQ8bGk+NVx1Yzc3YzogLTU8XC9saT5cclxuXHQ8bGk+Nlx1Yzc3YzogODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViM2M4XHVjNzQ0IFx1YmM4OCBcdWFkNmNcdWFjMDRcdWM3NDAgMn42XHVhZTRjXHVjOWMwXHVjNzc0XHVhY2UwIFx1Y2QxZCBcdWMyMThcdWM3ODVcdWM3NDAgMTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyNTAsMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2NcdWM3NTggXHVjMjE4XHVjNzc1IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwLDAwMCAmbGU7IFAgJmxlOyAxMCwwMDApIFx1YzIxOFx1Yzc3NVx1Yzc0MCBcdWNjYWIgXHViMGEwXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzIxOFx1Yzc3NVx1Yzc0NCBcdWM2MmNcdWI5YjAgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOFx1Yzc3NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhZDZjXHVhYzA0XHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDhcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiNDA5NyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlByb2ZpdHMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdXIgZnJpZW5kcyBoYXZlIGp1c3Qgb3BlbmVkIGEgbmV3IGJ1c2luZXNzLCBhbmQgeW91IHdhbnQgdG8gc2VlIGhvdyB3ZWxsIHRoZXkgYXJlIGRvaW5nLiBUaGUgYnVzaW5lc3MgaGFzIGJlZW4gcnVubmluZyBmb3IgYSBudW1iZXIgb2YgZGF5cywgYW5kIHlvdXIgZnJpZW5kcyBoYXZlIHJlY29yZGVkIHRoZWlyIG5ldCBwcm9maXQgb24gZWFjaCBkYXkuIFlvdSB3YW50IHRvIGZpbmQgdGhlIGxhcmdlc3QgdG90YWwgcHJvZml0IHRoYXQgeW91ciBmcmllbmRzIGhhdmUgbWFkZSBkdXJpbmcgYW55IGNvbnNlY3V0aXZlIHRpbWUgc3BhbiBvZiBhdCBsZWFzdCBvbmUgZGF5LiBGb3IgZXhhbXBsZSwgaWYgeW91ciBmcmllbmRzJnJzcXVvOyBwcm9maXRzIGxvb2tlZCBsaWtlIHRoaXM6PFwvcD5cclxuXHJcbjxwPkRheSAxOiAtMzxiciBcLz5cclxuRGF5IDI6IDQ8YnIgXC8+XHJcbkRheSAzOiA5PGJyIFwvPlxyXG5EYXkgNDogLTI8YnIgXC8+XHJcbkRheSA1OiAtNTxiciBcLz5cclxuRGF5IDY6IDg8XC9wPlxyXG5cclxuPHA+VGhlaXIgbWF4aW11bSBwcm9maXQgb3ZlciBhbnkgc3BhbiB3b3VsZCBiZSAxNCwgZnJvbSBkYXlzIDIgdG8gNi48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZXJlIHdpbGwgYmUgc2V2ZXJhbCB0ZXN0IGNhc2VzIGluIHRoZSBpbnB1dC4gRWFjaCB0ZXN0IGNhc2Ugd2lsbCBiZWdpbiB3aXRoIGFuIGludGVnZXIgTiAoMSAmbGU7IE4gJmxlOyAyNTAsMDAwKSBvbiBpdHMgb3duIGxpbmUsIGluZGljYXRpbmcgdGhlIG51bWJlciBvZiBkYXlzLiBPbiBlYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgd2lsbCBiZSBhIHNpbmdsZSBpbnRlZ2VyIFAgKC0xMDAgJmxlOyBQICZsZTsgMTAwKSwgaW5kaWNhdGluZyB0aGUgcHJvZml0IGZvciB0aGF0IGRheS4gVGhlIGRheXMgYXJlIHNwZWNpZmllZCBpbiBvcmRlci4gVGhlIGlucHV0IHdpbGwgZW5kIHdpdGggYSBsaW5lIHdpdGggYSBzaW5nbGUgMC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIG91dHB1dCBhIHNpbmdsZSBpbnRlZ2VyLCByZXByZXNlbnRpbmcgdGhlIG1heGltdW0gcHJvZml0IG92ZXIgYW55IG5vbi1lbXB0eSBzcGFuIG9mIHRpbWUuIFByaW50IGVhY2ggaW50ZWdlciBvbiBpdHMgb3duIGxpbmUgd2l0aCBubyBzcGFjZXMuIERvIG5vdCBwcmludCBhbnkgYmxhbmsgbGluZXMgYmV0d2VlbiBhbnN3ZXJzLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

ACM-ICPC > Regionals > North America > Southeast USA Regional > 2010 Southeast USA Regional Programming Contest G번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: zych1751