Bài tập thuật toán: Mua bán cổ phiếu

Đề bài: Cho 1 dãy số được sắp xếp theo thời gian mua và bán 1 cổ phiếu. Yêu cầu mua trước bán sau. Làm sao tính được lợi nhuận lớn nhất ?

Ví dụ: [10, 12, 5, 7, 6, 4, 8, 12, 3, 9] => kết quả đúng là mua 4, bán 12 và lợi nhuận 8

Với đề bài như này, thì mỗi lần mua thì mình phải đặt mốc mua, sau đó tìm mốc bán cổ phiếu và phải tính toán xem thời điểm mua bán này nó lời bao nhiêu.

Dưới đây là code javascript giải quyết đề bài.

function main(arr) {
  let resolve = { profit: 0 }
  let buy = sell = arr[0] // giả sử
  let actionBuy = true// sự kiện mua
  let i = 0
  while (i < arr.length) {
    // nếu phần tử đằng trước < đằng sau => mua
    if(arr[i] < arr[i + 1]) {
      if(actionBuy) buy = arr[i]
      actionBuy = false
    } else {
      sell = arr[i]
      // nếu thời điểm mua hiện tại lời hơn thời điểm trước
      // => lưu kết quả
      if((sell - buy) > resolve.profit) {
        resolve = {
          buy,
          sell,
          profit: sell - buy
        }
      }
      //  Bật lại sự kiện mua
      actionBuy = true
    }
    i++;
  }
  return resolve
}

Với đoạn code trên thì độ phức tạp của nó chỉ là O(n).

Các bạn có đáp án khác thì comment phía bên dưới để cho mọi người cùng tham khảo nhé. Cảm ơn các bạn đã đọc bài viết nay.

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *