시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 131 68 54 50.943%

문제

연종이는 창업했다. 오늘은 창업한지 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+XHVjNWI0XHViMjkwIFx1YjBhMCBcdWM1ZjBcdWM4ODVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc3NCBcdWIzYzhcdWM3NDQgXHViYzg4IFx1YWQ2Y1x1YWMwNFx1Yzc3NCBcdWM1YjhcdWM4MWNcdWM3NzhcdWM5YzAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2MjRcdWIyOThcdWM3NzQgXHVjYzNkXHVjNWM1XHVkNTVjXHVjOWMwIDZcdWM3N2MgXHViNDE4XHVjNWM4XHVhY2UwLCBcdWMyMThcdWM3NzVcdWM3NzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNFx1YWNlMCBcdWQ1NThcdWM3OTAuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MVx1Yzc3YzogLTM8XC9saT5cclxuXHQ8bGk+Mlx1Yzc3YzogNDxcL2xpPlxyXG5cdDxsaT4zXHVjNzdjOiA5PFwvbGk+XHJcblx0PGxpPjRcdWM3N2M6IC0yPFwvbGk+XHJcblx0PGxpPjVcdWM3N2M6IC01PFwvbGk+XHJcblx0PGxpPjZcdWM3N2M6IDg8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHViM2M4XHVjNzQ0IFx1YmM4OCBcdWFkNmNcdWFjMDRcdWM3NDAgMn42XHVhZTRjXHVjOWMwXHVjNzc0XHVhY2UwIFx1Y2QxZCBcdWMyMThcdWM3ODVcdWM3NDAgMTRcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiAoMSAmbGU7IE4gJmxlOyAyNTAsMDAwKSBcdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIE5cdWFjMWNcdWM3NTggXHVjOTA0XHVjNWQwXHViMjk0IFx1YjllNFx1Yzc3YyBcdWI5ZTRcdWM3N2NcdWM3NTggXHVjMjE4XHVjNzc1IFBcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwLDAwMCAmbGU7IFAgJmxlOyAxMCwwMDApIFx1YzIxOFx1Yzc3NVx1Yzc0MCBcdWNjYWIgXHViMGEwXHViZDgwXHVkMTMwIFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IDBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYyBcdWFjMDBcdWM3YTUgXHViOWNlXHVjNzQwIFx1YzIxOFx1Yzc3NVx1Yzc0NCBcdWM2MmNcdWI5YjAgXHVhZDZjXHVhYzA0XHVjNzU4IFx1YzIxOFx1Yzc3NVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjJlOCwgXHVhZDZjXHVhYzA0XHVjNzc0IFx1YmU0NFx1YzViNFx1Yzc4OFx1YzczY1x1YmE3NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQwOTciLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJQcm9maXRzIiwiZGVzY3JpcHRpb24iOiI8cD5Zb3VyIGZyaWVuZHMgaGF2ZSBqdXN0IG9wZW5lZCBhIG5ldyBidXNpbmVzcywgYW5kIHlvdSB3YW50IHRvIHNlZSBob3cgd2VsbCB0aGV5IGFyZSBkb2luZy4gVGhlIGJ1c2luZXNzIGhhcyBiZWVuIHJ1bm5pbmcgZm9yIGEgbnVtYmVyIG9mIGRheXMsIGFuZCB5b3VyIGZyaWVuZHMgaGF2ZSByZWNvcmRlZCB0aGVpciBuZXQgcHJvZml0IG9uIGVhY2ggZGF5LiBZb3Ugd2FudCB0byBmaW5kIHRoZSBsYXJnZXN0IHRvdGFsIHByb2ZpdCB0aGF0IHlvdXIgZnJpZW5kcyBoYXZlIG1hZGUgZHVyaW5nIGFueSBjb25zZWN1dGl2ZSB0aW1lIHNwYW4gb2YgYXQgbGVhc3Qgb25lIGRheS4gRm9yIGV4YW1wbGUsIGlmIHlvdXIgZnJpZW5kcyZyc3F1bzsgcHJvZml0cyBsb29rZWQgbGlrZSB0aGlzOjxcL3A+XHJcblxyXG48cD5EYXkgMTogLTM8YnIgXC8+XHJcbkRheSAyOiA0PGJyIFwvPlxyXG5EYXkgMzogOTxiciBcLz5cclxuRGF5IDQ6IC0yPGJyIFwvPlxyXG5EYXkgNTogLTU8YnIgXC8+XHJcbkRheSA2OiA4PFwvcD5cclxuXHJcbjxwPlRoZWlyIG1heGltdW0gcHJvZml0IG92ZXIgYW55IHNwYW4gd291bGQgYmUgMTQsIGZyb20gZGF5cyAyIHRvIDYuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGVyZSB3aWxsIGJlIHNldmVyYWwgdGVzdCBjYXNlcyBpbiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIHdpbGwgYmVnaW4gd2l0aCBhbiBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMjUwLDAwMCkgb24gaXRzIG93biBsaW5lLCBpbmRpY2F0aW5nIHRoZSBudW1iZXIgb2YgZGF5cy4gT24gZWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIHdpbGwgYmUgYSBzaW5nbGUgaW50ZWdlciBQICgtMTAwICZsZTsgUCAmbGU7IDEwMCksIGluZGljYXRpbmcgdGhlIHByb2ZpdCBmb3IgdGhhdCBkYXkuIFRoZSBkYXlzIGFyZSBzcGVjaWZpZWQgaW4gb3JkZXIuIFRoZSBpbnB1dCB3aWxsIGVuZCB3aXRoIGEgbGluZSB3aXRoIGEgc2luZ2xlIDAuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBvdXRwdXQgYSBzaW5nbGUgaW50ZWdlciwgcmVwcmVzZW50aW5nIHRoZSBtYXhpbXVtIHByb2ZpdCBvdmVyIGFueSBub24tZW1wdHkgc3BhbiBvZiB0aW1lLiBQcmludCBlYWNoIGludGVnZXIgb24gaXRzIG93biBsaW5lIHdpdGggbm8gc3BhY2VzLiBEbyBub3QgcHJpbnQgYW55IGJsYW5rIGxpbmVzIGJldHdlZW4gYW5zd2Vycy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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