Tính tổng lớn nhất trong mảng sao cho khoảng cách giữa các chỉ số không quá k

[dukksoocee (catsoougly412)]

Cho minh hỏi cách tìm tổng lớn nhất trong mảng sao cho khoảng cách giữa các chỉ số <= k.
(Cách nhanh : Chặt nhị phân) Cách trâu thì mình đã biết r
VD
INPUT
n = 4, k = 3;
1 6 4 2 3
OUTPUT 9
cảm ơn

[noname00 (HK boy)]

Ồ, 2 bạn học cùng lớp à?

Hỏi về tìm nhị phân

Mọi người cho em hỏi cách xử lí bài này với Tìm tổng lớn nhất sao cho chỉ khoảng cách từ 1 điểm được chọn tới các chỉ số <= k Ví dụ n = 4, k = 3 Giá trị Chỉ số 4 7 10 15 2 2 5 1 OUTPUT ==> 11 (Chọn điểm số 4 thì tổng lớn nhất 4+2+5 = 11 tương ứng với các chỉ số thoả mãn là 7, 2, 1 vì khoảng cách của chúng tới 4 đều <= 3) Ý tưởng1: Em nghĩ là bài này sử dụng tìm kiếm nhị phân nhưng làm vẫn chưa thành công Ý tưởng2 Duyệt Trâu bò cách này chỉ làm được 20-30% test… Mong mn gi…

[Ktoonovip (Dũng)]

Chào bạn,
Đây là giải theo cách mình hiểu do cái test của bạn ví dụ nó ảo quá mình không tài nào hiểu nổi.

Bây giờ ta gọi F[i] là cách tìm tổng lớn nhất kết thúc tại vị trí i.
Ta có: F[i] = max(F[i -1], F[i - 2], ..., F[i - k]) + a[i];
Bây giờ vậy của bạn là tối ưu đoạn tìm max.
Đoạn này có thể dùng dequeue để tối ưu.
Bạn tham khảo bài toán này: https://vn.spoj.com/problems/MINK/
ĐPT: O (n)

[rogp10]

Bài đó là điểm trên trục Ox mà

@Ktoonovip

Đoạn này có thể dùng stack để tối ưu.

dequeue. Chỉ cần một circular buffer thay vì include.

[Ktoonovip (Dũng)]

Ohh sorry e lại ẩu rồi. Đoạn này đúng là dùng dequeue để tối ưu.
E đã fix. Thanks a nhiều :3