Thay vì tìm trực tiếp số tiền lớn nhất lấy được thỏa mãn không vào ~k~ ngôi nhà liên tiếp, ta sẽ tìm số tiền nhỏ nhất có thể lấy được nếu đi vào một dãy con gồm các ngôi nhà, với hai ngôi nhà liên tiếp mà Seiga đi vào sẽ có khoảng cách không quá ~k~.

Gọi ~f_i~ là tổng số tiền ít nhất lấy được khi đi đến ngôi nhà thứ ~i~. Công thức sẽ là ~f_i = min(f_{i-j}) + a_i~ với mọi ~1 \le j \le k~. Sử dụng deque để tìm nhanh ~min(f_{i-j})~ trong ~O(n)~.

Đáp án sẽ là ~sum - min(f)~.

Tổng độ phức tạp: ~O(n)~.