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

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
hhoangcpascal
Dạng bài
Điểm: 400 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho dãy \(A\) gồm \(N\) phần tử là các số nguyên dương \(A_1, A_2, ..., A_N\). Dãy \(C\) được gọi là dãy con tăng độ dài \(K\) của \(A\) nếu thoả mãn các điều kiện sau:

  • \(K \geq 1\).
  • \(1 \leq i_1 < i_2 < i_3 < ... < i_K \leq N\).
  • \(C_1 = A_{i_1}, C_2 = A_{i_2}, ..., C_K = A_{i_K}\).
  • \(C_1 < C_2 < ... < C_K\) nếu \(K \geq 2\)

Yêu cầu: Gọi \(SumC = \sum\limits_{i=1}^K C_i\). Tìm \(SumC\) lớn nhất có thể của dãy \(C\).

Input

  • Dòng thứ nhất gồm số nguyên dương \(N\).
  • Dòng thứ hai gồm \(N\) số nguyên dương \(A_1, A_2, A_3, ..., A_N\).

Output

  • In ra một số nguyên dương duy nhất là kết quả bài toán.

Constraints

  • \(N\leq 10^5\)
  • \(A_i\leq 10^9\)

Scoring

  • Subtask \(1\) (\(50\%\) số điểm): \(N\leq 10^3\).
  • Subtask \(2\) (\(50\%\) số điểm): Không có ràng buộc gì thêm.

Example

Test 1

Input 
5
1 2 3 5 4
Output 
11

Bình luận