Nhận xét:

• Đây là bài toán sử dụng các hàm tổng tiền tố và tổng hậu tố,
• Khoảng cần tính tổng không thay đổi, vì vậy không cần quản lý các tổng này bằng các cây.

Nếu Hermione chọn các phần thưởng từ ~p~ đến ~p+k-1~ thì tổng giá trị t có được sẽ là:

~t= a_p + a_{p+1} + ... + a _{p+k-1} = s_{p+k-1} – s_{p-1},~

trong đó ~s_0 = 0, s_i = s_{i-1} + a_i , i=1 \div n ~.

Harry có thể chọn phần thưởng cho mình ở bên trái hay bên phải dãy Hermione đã chọn.

Nếu chọn bên trái thì tổng giá trị nhận được sẽ là: ~vleft_p~

Nếu chọn bên phảii thì tổng giá trị nhận được sẽ là:~vright_ {p+k}~

Giữa hai giá trị này cần chọn giá trị lớn nhất.

Trong các công thức trên:

~ vleft_p =\left\{\begin{matrix} 0, i=0 \div k-1 \\ max (vleft_ {i-1}, s_i - s_ {i-k}), i= k \div n-k+1 \end{matrix}\right. ~

~ vright_ {p+k} =\left\{\begin{matrix} 0, i=n \div n- k+1 \\ max (vright_ {i+1}, s_{i+k-1} - s_ {i-1}), i= n-k+1 \div k+1 \end{matrix}\right. ~

Để tìm ~x~ cần duyệt với mọi ~ i~ từ ~1~ đến ~n-k+1~, tính: ~x = min(x, max(vleft_ {i-1}, vright_{i+k} )) ~

Độ phức tạp của giải thuật: O(n)