Bài toán đầu tư chứng khoán
Harry làm việc ở một công ty tư vấn đầu tư chứng khoán. Nhiệm vụ của Harry là phân tích sự giao động chỉ số chứng khoán hàng ngày của sàn giao dịch, từ đó có thể các thông tin hữu ích để tư vấn cho các nhà đầu tư.
Nhiệm vụ của Harry trong đề án đang thực hiện là như sau: Cho dãy chỉ số chứng khoán của n ngày liên tiếp. Cần phải tìm ra dãy con dài nhất sao cho chênh lệch hai chỉ số liên tiếp không ít hơn k. Ví dụ, với dãy chỉ số chứng khoán 1014, 1024, 1034, 1045, 1030, 998 và k = 15 thì dãy con 1014, 1034, 998 là chấp nhận được, nhưng dãy 1014, 1045,1030, 998 là dãy con dài nhất cần tìm.
Yêu cầu: Cho n, k và dãy các chỉ số chứng khoán (1 ≤ n ≤ 100 000, 1 ≤ k ≤ 109). Các chỉ số chứng khoán là những số nguyên dương, có giá trị không vượt quá 109. Hãy chỉ ra dãy con dài nhất thỏa mãn các điều kiện đã nêu.
Dữ liệu: Vào từ file văn bản FINANCIAL.INP
- Dòng đầu tiên chứa hai số nguyên n và k,
- Dòng thứ 2 chứa n số nguyên – các chỉ số chứng khoán.
Kết quả: Đưa ra file văn bản FINANCIAL.OUT:
- Dòng đầu tiên đưa ra độ dài của dãy con tìm được,
- Dòng thứ hai – các chỉ số thuộc dãy con theo trình tự xuất hiện. Nếu có nhiều dãy con cùng độ dài thì đưa ra dãy tùy ý.
Thuật toán giải bài toán đầu tư chứng khoán
Để giải quyết bài toán này, ta có thể sử dụng thuật toán dynamic programming với cách tiếp cận tương tự như bài toán tìm dãy con tăng dài nhất (Longest Increasing Subsequence).
Đặt L[i] là độ dài dãy con dài nhất kết thúc tại vị trí i. Ta có thể tính L[i] bằng cách duyệt các vị trí j < i và kiểm tra xem giá trị a[i] và a[j] có chênh lệch ít nhất k hay không. Nếu có thì L[i] sẽ bằng max(L[j]) + 1. Trong trường hợp không có vị trí j nào thỏa mãn yêu cầu, thì L[i] = 1.
Sau khi tính được tất cả các giá trị L[i], ta tìm giá trị lớn nhất trong mảng L và xây dựng lại dãy con tương ứng. Cách xây dựng dãy con này có thể được thực hiện bằng cách duyệt ngược từ vị trí cuối cùng của dãy con và chọn các vị trí j mà có L[j] = L[i] – 1 và a[j] và a[i] chênh lệch ít nhất k.
Độ phức tạp của thuật toán này là O(n^2), do ta phải duyệt lại từng phần tử trong mảng đầu vào để tính L[i]. Tuy nhiên, nếu sử dụng các cấu trúc dữ liệu và thuật toán phù hợp, ta có thể cải thiện độ phức tạp lên O(n log n).
Cài đặt bài toán với Python
def longest_subsequence(n, k, arr):
dp = [1] * n # khởi tạo mảng DP ban đầu, tất cả đều bằng 1
prev = [-1] * n # mảng lưu vị trí phần tử trước trong dãy con dài nhất
for i in range(1, n):
for j in range(i):
if abs(arr[i] - arr[j]) >= k and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
prev[i] = j
# tìm vị trí của phần tử có giá trị lớn nhất trong mảng DP
max_len_idx = 0
for i in range(n):
if dp[i] > dp[max_len_idx]:
max_len_idx = i
# tạo mảng dãy con dài nhất bằng cách truy vết lại các vị trí phần tử trước
seq = []
while max_len_idx != -1:
seq.append(arr[max_len_idx])
max_len_idx = prev[max_len_idx]
seq.reverse() # đảo ngược lại để trả về theo thứ tự ban đầu
return len(seq), seq
# đọc dữ liệu từ file FINANCIAL.INP và gọi hàm xử lý
with open("FINANCIAL.INP", "r") as f:
n, k = map(int, f.readline().split())
arr = list(map(int, f.readline().split()))
length, subseq = longest_subsequence(n, k, arr)
# ghi kết quả vào file FINANCIAL.OUT
with open("FINANCIAL.OUT", "w") as f:
f.write(str(length) + "\n")
f.write(" ".join(map(str, subseq)))
Cài đặt bài toán với C++
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, k;
int a[MAXN];
int L[MAXN], pre[MAXN];
int main() {
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
L[i] = 1;
pre[i] = -1;
}
int max_len = 1, last = 1;
for (int i = 2; i <= n; i++) {
for (int j = i - 1; j >= 1; j--) {
if (abs(a[i] - a[j]) >= k && L[j] + 1 > L[i]) {
L[i] = L[j] + 1;
pre[i] = j;
if (L[i] > max_len) {
max_len = L[i];
last = i;
}
}
}
}
cout << max_len << endl;
while (last != -1) {
cout << a[last] << " ";
last = pre[last];
}
return 0;
}