Subtask 1 : n <= 20 ; W <= S
- Sử dụng Backtracking
- ĐPT : O(2 ^ n)
Sutask 2 : n <= 50; W = S
- Chính là bài dãy con tăng (LIS) cơ bản
- ĐPT : O(n ^ 2)
Subtask 3 : n <= 50; W <= S
- Quy hoạch động : F[i][j] là dãy con tăng dài nhất từ 1 đến i có tổng trọng số không quá j.
- ĐPT : O(n ^ 2 * W)
Subtask 4 : n <= 500; W <= S
- Cải tiến từ Subtask 3 : Ta sẽ sử dụng 1 cây BIT để quản lí
- ĐPT : O(n * log(n) * W)
Subtask 5: n <= 50000; W = S
- Cải tiến từ subtask 2 : Ta sẽ sử dụng 1 cây BIT để quản lí
- ĐPT O(n * log(n))