Tóm tắt đề bài

Cho một dãy gồm \(n\) món quà, món quà thứ \(i\) có giá trị \(A_i\). Cần chọn ra hai đoạn con liên tiếp, mỗi đoạn có độ dài đúng bằng \(k\), sao cho hai đoạn này không giao nhau (không đè lên nhau) và tổng giá trị các phần tử trong hai đoạn là lớn nhất.

Phân tích

• Ràng buộc: \(n \le 10^5\), \(k \le n/2\), \(A_i \le 10^9\).

• Mục tiêu: Tìm hai chỉ số \(i\) và \(j\) sao cho \(1 \le i, j \le n-k+1\) và \(|i - j| \ge k\), nhằm tối đa hóa tổng:

  \[ \sum_{x=i}^{i+k-1} A_x + \sum_{y=j}^{j+k-1} A_y \]

• Nhận xét:

  • Với \(n = 10^5\), ta không thể duyệt mọi cặp \((i, j)\) vì độ phức tạp sẽ là \(O(n^2)\). Cần một cách tiếp cận tối ưu hơn, khoảng \(O(n)\).
  • Giả sử ta cố định đoạn thứ hai kết thúc tại vị trí \(i\) (tức là đoạn \([i-k+1, i]\)). Khi đó, đoạn thứ nhất phải nằm hoàn toàn bên trái đoạn này, tức là kết thúc tại một vị trí \(j\) sao cho \(j \le i-k\).
  • Để tổng lớn nhất, với mỗi vị trí kết thúc \(i\) của đoạn thứ hai, ta cần tìm một đoạn độ dài \(k\) ở phía trước có tổng lớn nhất.

Hướng giải quyết

Bước 1: Tiền xử lý mảng cộng dồn

Sử dụng mảng cộng dồn (Prefix Sum) \(S\) để tính nhanh tổng của một đoạn bất kỳ:

• \(S_i = A_1 + A_2 + \dots + A_i\).
• Tổng đoạn \([i-k+1, i]\) là: \(T_i = S_i - S_{i-k}\).

Bước 2: Sử dụng mảng Max Prefix

Gọi \(L_i\) là giá trị lớn nhất của tổng một đoạn độ dài \(k\) kết thúc tại hoặc trước vị trí \(i\).

• Công thức: \(L_i = \max(L_{i-1}, T_i)\) với \(i \ge k\).
• \(L_i\) giúp ta biết được: "Nếu ta chọn một đoạn kết thúc từ vị trí \(i\) trở về trước, tổng lớn nhất có thể đạt được là bao nhiêu?".

Bước 3: Duyệt và tìm kết quả

Duyệt vị trí kết thúc \(i\) của đoạn thứ hai từ \(2k\) đến \(n\):

• Đoạn thứ hai là \([i-k+1, i]\) có tổng là \(T_i\).
• Đoạn thứ nhất tốt nhất nằm bên trái nó sẽ kết thúc tại một vị trí nào đó từ \(k\) đến \(i-k\). Tổng lớn nhất của đoạn này chính là \(L_{i-k}\).
• Tổng của hai đoạn là: \(CurrentSum = T_i + L_{i-k}\).
• Kết quả cuối cùng là giá trị lớn nhất của \(CurrentSum\) tìm được.

Độ phức tạp

• Thời gian: \(O(n)\) để tính mảng cộng dồn, mảng \(L\) và duyệt tìm kết quả.
• Bộ nhớ: \(O(n)\) để lưu trữ mảng \(A\), \(S\) và \(L\).