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 ...