VDSEQ01 - Trò chơi với dãy số
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 512 megabyte
Đăng bởi: phuleethanh

Tèo và Tí rất thích những con số, hai bạn hôm nay hẹn gặp nhau cùng chơi trò chơi với dãy số của mình (dãy số này là chọn trước, cố định không được xáo trộn dãy khi chơi, có số âm có số dương).

Trò chơi có thể lệ như sau: Mỗi người có một dãy số của riêng mình, mỗi lượt chơi mỗi người được chọn ra từ dãy số của mình một đoạn phần tử liên tục, tính tổng của đoạn này. Ai có tổng lớn hơn người đó thắng lượt chơi đó.

Tèo muốn giành chiến thắng ở lượt đầu tiên để tạo khí thế, nên Tèo quyết định sẽ chọn ra đoạn nào có tổng lớn nhất có thể. Tuy nhiên dãy số khá dài nên Tèo khá bối rối. Bạn hãy lập trình giúp tèo chọn ra đoạn phần tử ở lượt chơi đầu tiên này.

Dữ liệu vào:

- Dòng đầu tiên là số nguyên dương N (0<=n<=2*105)

- Các dòng sau là dãy số A1, A2,..., An. (|Ai|<=109)

Kết quả:

- Một số duy nhất là tổng lớn nhất sẽ chơi ở lượt đầu tiên.

Ví dụ

  • input
    10
    1
    3
    5
    -4
    -5
    1
    -5
    3
    1
    -1
    output
    9
Back to Top