Subtask 1: Ta ta đơn giản duyệt qua tất cả các cách lựa chọn tập hợp đoạn và kiểm tra điều kiện đề bài. Độ phức tạp: ~O(2^S.S^2)~ với ~S~ là số lượng đoạn ~[l,r]~.

Subtask 2: Với ~K=2~, ta có thể xây dựng tập hợp bao gồm một đoạn có độ dài ~2~ hoặc hai đoạn có độ dài ~1~. Duyệt qua tất cả các cách chọn tập hợp với độ phức tạp ~O(N^2)~.

Subtask 3: Ta ưu tiên chọn một đoạn có độ dài ~2~ hoặc hai đoạn có độ dài ~1~ có giá trị chi phí lớn nhất. Sắp xếp các đoạn theo chi phí và tìm kết quả. Độ phức tạp: ~O(N.log(N))~.

Subtask 4: Gọi chi phí của đoạn ~[l,r]~ là ~f(l,r) = |b_r - a_l| + |b_l - a_r|~. Quy hoạch động với trạng thái như sau:

Gọi ~dp[i][j]~ (~1 \le i \le N~, ~1 \le j \le K~) là chi phí lớn nhất của tập hợp đoạn từ ~1~ đến ~i~ có tổng độ dài các đoạn bằng ~j~. Ta xây dựng công thức truy hồi sau:

~dp[i][j]=max(dp[i-1][j], \; dp[i-l][j-l] + f(i-l+1,i)~ với ~1 \le l \le j)~.

Công thức trên với ý nghĩa: Ta có thể lựa chọn giữa việc giữ nguyên trạng thái ~i-1~ trước đó (không sử dụng đoạn kết thúc tại ~i~) hoặc thêm một đoạn độ dài ~l~ kết thúc tại ~i~ vào tập hợp đã có. Đáp án của bài toán là ~dp[N][K]~.

Độ phức tạp: ~O(N^2.K)~.

Subtask 5: Ta có thể biến đổi cách tính chi phí như sau:

~f(l,r) = |b_r - a_l| + |b_l - a_r| = max\{- a_r + b_r - a_l + b_l, \; a_r + b_r - a_l - b_l, \; -a_r - b_r + a_l + b_l, \; a_r - b_r + a_l - b_l\}~

Ngoài ra, khi tính ~dp[i][j]~, ta quay về so sánh giữa các giá trị ~dp[i-l][j-l]~. Các giá trị này được gọi là giá trị đường chéo khi biểu diễn ~dp~ thành một ma trận hai chiều. Các cặp chỉ số ~(i-l,j-l)~ này có điểm chung là đều có cùng giá trị ~i-j~. Từ đó, cùng với cách biến đổi biểu thức chi phí ở trên, ta có thể duy trì ~4~ kiểu kết hợp ~dp[i][j]-a_{i+1}+b_{i+1}~, ~dp[i][j]-a_{i+1}-b_{i+1}~, ~dp[i][j]+a_{i+1}+b_{i+1}~ và ~dp[i][j]+a_{i+1}-b_{i+1}~.

Khi đó, để tính ~dp[i][j]~ nếu lựa chọn thêm một đoạn độ dài ~l~, ta chỉ cần tìm giá trị lớn nhất trong số ~4~ cách kết hợp trên.

Độ phức tạp: ~O(N.K)~