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 < . . . < ik ≤ n.
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.