Dãy con có tổng lớn nhất


Submit solution

Points: 2
Time limit: 1.0s
Memory limit: 98M

Author:
Problem type

Cho một dãy số nguyên a1,a2 … an, một dãy con được sinh ra bằng cách lấy các phần tử bất kì (không nhất thiết phải liên tục) nhưng thứ tự phải được giữ nguyên đảm bảo phần tử nào đứng trước trong dãy ban đầu thì cũng phải đứng trước trong dãy con. Nhiệm vụ của bạn tìm tổng lớn nhất trong tổng của tất cả các dãy con sinh ra bởi dãy số nguyên ban đầu. Lưu ý: dãy con có thể chỉ có 1 phần tử.

Đầu vào

Dòng 1 chứa số nguyên dương n \((1<=n<=10^6)\)

Dòng 2 chứa các phần tử của dãy là các số nguyên có giá trị tuyệt đối không quá \(10^3\)

Đầu ra

Một số nguyên dương duy nhất là tổng lớn nhất

Ví dụ

Input

5
-1 3 -2 5 6

Output

14

Giải thích

Với dãy con {3,5,6} ta thu được tổng lớn nhất là: 3+5+6=14


Comments


  • 2
    cotyey  commented on Nov. 18, 2020, 4:45 a.m.

    Bài này làm gì mà set java tận 2s nhỉ, chạy bt mà ?


    • 2
      DuyAnhhh  commented on Nov. 18, 2020, 5:11 a.m.

      À em set để test anh ạ,quên chưa chỉnh lại :v


  • 2
    TICHPX  commented on Nov. 13, 2020, 10:40 a.m.

    Đây là dãy con nào đó không liên tục. Còn nói tới dã đơn điệu là dãy tăng dần hoặc dãy giảm dần mới là đơn điệu


    • 2
      DuyAnhhh  commented on Nov. 13, 2020, 3:44 p.m.

      Để em sửa lại đề cho chuẩn