Đề 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.