Solution từ bedao

Nhận xét: Đề bài yêu cầu các phần tử được chọn không là liên tiếp nhưng không quan trọng thứ tự ~(i < j)~ thế nên cách tối ưu để chọn là sắp xếp mảng các phân tử tăng dần ~\rightarrow~ Phần tử lớn nhất luôn nằm ở đầu đoạn chọn và phần tử bé nhất luôn nằm ở cuối đoạn chọn.

Qua đó, duy trì một đoạn có độ dài ~[r-N+1, r]~ rồi lấy ~max(sum(r-N+1, r))~ và đoạn duy trì phải thỏa ~a_r - a_{r-N+1} \leq K~. Để tối ưu cách lấy ~sum(r-N+1,r)~ ta có thể sử dụng ~prefix~ ~sum~ để tính trong ~O(1)~.

Solution được đóng góp từ bạn SPyofgame

Ta chỉ cần sắp xếp lại mảng theo giá trị tăng dần, chọn các đoạn ~[l, r]~ gồm ~N~ người và kiểm tra xem đoạn này có thỏa mãn điều kiện ~max(a[l \dots r]) - min(a[l \dots r]) \leq K \Leftrightarrow a[r]-a[l] \leq K~ hay không.

Có thể tính tổng giá trị của một đoạn từ ~l~ đến ~r~ trong ~O(1)~ bằng cách sử dụng mảng cộng dồn.

Mảng cộng dồn được tính theo công thức : ~sum[i] = sum[i-1]+a[i]~ với ~1 \leq i \leq M~ .

Sau khi đã có mảng cộng dồn, tổng giá trị đoạn từ ~l~ đến ~r~ bằng ~sum[r] - sum[l-1]~.

Vậy bài này có thể làm trong ~O(n\ log n)~, trong đó:

• ~O(n\ log n)~ để sắp xếp

• ~O(n)~ để dựng mảng cộng dồn

• ~O(n)~ để duyệt qua các đoạn và cập nhật kết quả