Câu hỏi

Giả sử như bạn có thông tin về giá của một món hàng trong một khoảng thời gian nào đó. Tìm ngày bạn sẽ mua, và ngày bạn sẽ bán món hàng đó để đạt được lợi nhuận cao nhất.

Đầu vào: một danh sách các giá trị thực là giá của món hàng từng ngày.

Đầu ra: hai chỉ mục trong danh sách là ngày mua, và ngày bán.

Ví dụ: với dữ liệu vào [10, 13, 9, 10, 11], thì kết quả là (0, 1) ý là mua ngày 0 với mức giá 10, bán ra ngày 1 với mức giá 13, lợi nhuận cao nhất là 3 đơn vị.

Phân tích

Gọi danh sách đầu vào là A. Câu hỏi này yêu cầu chúng ta tìm hai chỉ mục x và y trong A sao cho A[y] - A[x] lớn nhất, với điều kiện x < y.

Đặt min_x là chỉ mục của giá thấp nhất trong danh sách A. Khi xét đến phần tử i trong danh sách A, ta sẽ gặp một số trường hợp sau:

Giá giảm A[i] < A[min_x]

Đây là cơ hội mua vào nên ta sẽ đặt min_x = i.

Giá tăng A[i] >= A[min_x]

Đây là cơ hội bán ra nên ta sẽ phải xét thêm A[i] - A[min_x] > A[y] - A[x], tức là bán vào lúc này có lời hơn lúc trước không. Nếu có, ta sẽ cập nhật y, x = i, min_x.

Cài đặt

def solve(A):
  x = y = min_x = 0
  for i in xrange(1, len(A)):
    if A[i] < A[min_x]:
      min_x = i
    elif A[i] - A[min_x] >= A[y] - A[x]:
      x, y = min_x, i
  return (x, y)

assert(solve([10, 13, 9, 10, 11]) == (0, 1))