BITONIC - Dãy hình nón
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ớ: 128 megabyte
Đăng bởi: admin

Dãy số b1, b2, . . ., bm được gọi là hình nón nếu tồn tại j sao cho b1<b2< . . .<bj>bj+1> . . .>bm (1 <j<m). Theo định nghĩa ta thấy dãy số hình nón phải có ít nhất 3 phần tử.


Cho dãy số nguyên a1, a2, . . ., an. Dãy số ai1, ai2, . . ., aik được gọi là dãy con của dãy đã cho nếu 1 ≤ i1 < i2 < . . . < ikn.

Yêu cầu:  Cho dãy số nguyên, các số ở hệ thập phân. Hãy xác định dãy con hình nón có tổng các chữ số lớn nhất và đưa ra tổng này.

Dữ liệu vào:

- Dòng đầu tiên chứa số nguyên n (3 ≤ n ≤ 1 000),

- Dòng thứ 2 chứa n số nguyên a1, a2, . . ., an (1 ≤ ai ≤ 105).

Kết quả ra: Một số nguyên là kết quả tìm được.

Ví dụ

  • input
    4
    2 1 3 1
    output
    6
Back to Top