Nhịp tăng có tổng lớn nhất

Bối cảnh và bài toán

Một chuỗi điểm đo có thể chứa cả số âm. Bạn cần chọn một dãy con giữ nguyên thứ tự, các giá trị tăng nghiêm ngặt.

Yêu cầu

Tìm tổng lớn nhất của một dãy con tăng nghiêm ngặt không rỗng.

Input

Dòng 1: n. Dòng 2: a_1..a_n.

Output

In tổng lớn nhất.

Ràng buộc

• 1 <= n <= 5000
• -10^5 <= a_i <= 10^5

Chấm điểm

Ví dụ 1

Input

7
1 101 2 3 100 4 5

Output

106

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

5
-5 -1 -3 -2 -4

Output

-1

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: FULLHOUSE DEV – Self-generated.