Bài toán: Dương Quá đi bắt dế

Quách Phù bấy giờ đã tỉnh ngủ, thấy Dương Quá , mừng rỡ nói:
- Anh đi đâu đến bây giờ mới thấy mặt
Dương Quá trả lời:
- Tôi đi bắt dế ! Thật vui đáo để.
Quách Phù bĩu môi hỏi lại:
- Vui gì tuồng chơi dế !Anh thấy vui thế nào ?
Dương Quá kể:
- Trời ơi ! Sao lại không vui ! Này, một con dế lớn đấu với ba con dế nhỏ, rồi hai con dế nhỏ nữa phụ lực. Thế là tất cả có năm con dế nhỏ đấu với một con dế lớn. Nhưng con dế lớn một mình cự cả năm con dế nhỏ, hẩy con này ngã bên này, con kia ngã bên kia..
Nói đến đây Dương Quá im bặt, khiến cho Quách Phù tò mò hỏi:
- Thế rồi sao nữa ?
Dương Quá chẩu miệng nói:

- Cho một mảng gồm n phần tử, n là số nguyên dương không quá 1 vạn và trị tuyệt đối của mỗi phần tử không quá 30. Ta thực hiện thao tác sau trên mảng:
+ Chọn ra các đoạn khác rỗng gồm các phần tử liên tiếp trên mảng [l,r] có tổng giá trị các phần tử là lớn nhất (Có thể có nhiều đoạn như vậy). Ứng với mỗi đoạn như vậy, ta loại bỏ đi phần tử có giá trị lớn nhất và sau đó tính lại tổng các phần tử của đoạn đó (sau khi loại bỏ phần tử lớn nhất). Nhiệm vụ của bạn là in ra tổng có giá trị lớn nhất trong số các tổng sau khi bị biến đổi. (Để hiểu rõ hơn, các bạn có thể đọc thêm phần ví dụ phía dưới)

Cấu trúc input và output:
+ Dòng đầu tiên chứa số n - số phần tử của mảng
+ Dòng thứ hai chứa n số nguyên a_1,a_2,...,a_n.
Ví dụ:
Input 1:
5
5 -2 10 -1 4
Output 1:
6
* Giải thích: Ở đây ta chỉ có 1 đoạn [1,5] là có tổng giá trị các phần tử lớn nhất là 5-2+10-1+4=16. Sau đó ta loại bỏ đi phần tử có giá trị lớn nhất là 10. Khi đó tổng còn lại là 6. Vì chỉ có duy nhất một tổng nên đây cũng là kết quả của bài toán.
Input 2:
8
5 2 5 3 -30 -30 6 9
Output 2:
10
* Giải thích: Ở đây ta có hai đoạn [1,4] và [7,8] là có tổng giá trị các phần tử lớn nhất là 15.
+ Đối với đoạn [1,4], ta loại bỏ đi phần tử có giá trị lớn nhất  là 5: Khi đó tổng còn lại là 10.
+ Đối với đoạn [7,8], ta loại bỏ đi phần tử có giá trị lớn nhất  là 9: Khi đó tổng còn lại là 6.
Vì max(10,6)=10. Nên kết quả của bài toán là 10.
Input 3:
3
-10 6 -15
Output 3:
0
* Giải thích: Ở đây ta chỉ có duy nhất một đoạn [2,2] là có tổng giá trị các phần tử lớn nhất là 6. Sau khi ta loại bỏ phần tử này đi thì tổng còn lại là 0. Do đó kết quả của bài toán là 0.

 

Nhận xét