시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 66 38 31 57.407%

문제

연종이는 창업했다. 오늘은 창업한지 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+Nlx1Yzc3YzogODxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlx1Yzc3NFx1YjU0YywgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWIzYzhcdWM3NDQgXHViYzg4IFx1YWQ2Y1x1YWMwNFx1Yzc0MCAyfjZcdWFlNGNcdWM5YzBcdWM3NzRcdWFjZTAgXHVjZDFkIFx1YzIxOFx1Yzc4NVx1Yzc0MCAxNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuICgxICZsZTsgTiAmbGU7IDI1MCwwMDApIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWU0XHVjNzdjIFx1YjllNFx1Yzc3Y1x1Yzc1OCBcdWMyMThcdWM3NzUgUFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAsMDAwICZsZTsgUCAmbGU7IDEwLDAwMCkgXHVjMjE4XHVjNzc1XHVjNzQwIFx1Y2NhYiBcdWIwYTBcdWJkODBcdWQxMzAgXHVjMjFjXHVjMTFjXHViMzAwXHViODVjIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjMjE4XHVjNzc1XHVjNzQ0IFx1YzYyY1x1YjliMCBcdWFkNmNcdWFjMDRcdWM3NTggXHVjMjE4XHVjNzc1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViMmU4LCBcdWFkNmNcdWFjMDRcdWM3NzQgXHViZTQ0XHVjNWI0XHVjNzg4XHVjNzNjXHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MDk3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUHJvZml0cyIsImRlc2NyaXB0aW9uIjoiPHA+WW91ciBmcmllbmRzIGhhdmUganVzdCBvcGVuZWQgYSBuZXcgYnVzaW5lc3MsIGFuZCB5b3Ugd2FudCB0byBzZWUgaG93IHdlbGwgdGhleSBhcmUgZG9pbmcuIFRoZSBidXNpbmVzcyBoYXMgYmVlbiBydW5uaW5nIGZvciBhIG51bWJlciBvZiBkYXlzLCBhbmQgeW91ciBmcmllbmRzIGhhdmUgcmVjb3JkZWQgdGhlaXIgbmV0IHByb2ZpdCBvbiBlYWNoIGRheS4gWW91IHdhbnQgdG8gZmluZCB0aGUgbGFyZ2VzdCB0b3RhbCBwcm9maXQgdGhhdCB5b3VyIGZyaWVuZHMgaGF2ZSBtYWRlIGR1cmluZyBhbnkgY29uc2VjdXRpdmUgdGltZSBzcGFuIG9mIGF0IGxlYXN0IG9uZSBkYXkuIEZvciBleGFtcGxlLCBpZiB5b3VyIGZyaWVuZHMmcnNxdW87IHByb2ZpdHMgbG9va2VkIGxpa2UgdGhpczo8XC9wPlxyXG5cclxuPHA+RGF5IDE6IC0zPGJyIFwvPlxyXG5EYXkgMjogNDxiciBcLz5cclxuRGF5IDM6IDk8YnIgXC8+XHJcbkRheSA0OiAtMjxiciBcLz5cclxuRGF5IDU6IC01PGJyIFwvPlxyXG5EYXkgNjogODxcL3A+XHJcblxyXG48cD5UaGVpciBtYXhpbXVtIHByb2ZpdCBvdmVyIGFueSBzcGFuIHdvdWxkIGJlIDE0LCBmcm9tIGRheXMgMiB0byA2LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlcmUgd2lsbCBiZSBzZXZlcmFsIHRlc3QgY2FzZXMgaW4gdGhlIGlucHV0LiBFYWNoIHRlc3QgY2FzZSB3aWxsIGJlZ2luIHdpdGggYW4gaW50ZWdlciBOICgxICZsZTsgTiAmbGU7IDI1MCwwMDApIG9uIGl0cyBvd24gbGluZSwgaW5kaWNhdGluZyB0aGUgbnVtYmVyIG9mIGRheXMuIE9uIGVhY2ggb2YgdGhlIG5leHQgTiBsaW5lcyB3aWxsIGJlIGEgc2luZ2xlIGludGVnZXIgUCAoLTEwMCAmbGU7IFAgJmxlOyAxMDApLCBpbmRpY2F0aW5nIHRoZSBwcm9maXQgZm9yIHRoYXQgZGF5LiBUaGUgZGF5cyBhcmUgc3BlY2lmaWVkIGluIG9yZGVyLiBUaGUgaW5wdXQgd2lsbCBlbmQgd2l0aCBhIGxpbmUgd2l0aCBhIHNpbmdsZSAwLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgb3V0cHV0IGEgc2luZ2xlIGludGVnZXIsIHJlcHJlc2VudGluZyB0aGUgbWF4aW11bSBwcm9maXQgb3ZlciBhbnkgbm9uLWVtcHR5IHNwYW4gb2YgdGltZS4gUHJpbnQgZWFjaCBpbnRlZ2VyIG9uIGl0cyBvd24gbGluZSB3aXRoIG5vIHNwYWNlcy4gRG8gbm90IHByaW50IGFueSBibGFuayBsaW5lcyBiZXR3ZWVuIGFuc3dlcnMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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