30 ngày chống COVID cùng Leetcode | Ngày 05
Giả sử bạn là một nhà đầu tư, trong một thời điểm chỉ được thực hiện một giao dịch là mua hoặc là bán, cho một danh sách tỉ giá lên xuống trong quá khứ, hãy tính lợi nhuận tối đa bạn có thể mua được nếu bạn là một nhà đầu tư thông thái.
Đề bài rất là hay đúng không.
Điểm không thực tế của bài toán này đó là tại sao nó không được áp dụng trong kinh tế bởi vì đơn giản nó chỉ thống kê dữ liệu trong quá khứ rồi tối ưu, chứ không có một thuật toán tiên đoán lợi nhuận gì phức tạp cả, nhưng làm tốt bài toán này, ta có thể dễ dàng hình dung tốt hơn về thị trường đầu tư.
Với ví dụ 1, danh sách [7,1,5,3,6,4], khá là khó hình dung, ta sẽ thử vẽ nó bằng biểu đồ:
Ta có nhận xét, thời điểm ta sẽ giao dịch sẽ là thời điểm mà số liệu đang nằm ở vị trí thung lũng (1) (3), hoặc đang ở vị trí đỉnh (5) (6). Bởi sau thung lũng sẽ là đỉnh mà sau đỉnh thì là thung lũng.
Như thế có một giải pháp ở đây là lợi nhuận tối đa ta thu được sẽ bằng hiệu của điểm cao nhất trừ điểm thấp nhất trong 1 khoảng thời gian nào đó.
Dù đã Apcept trên Leetcode, nhưng tôi thấy hình như thuật toán này có vấn đề ?
Liệu có trường hợp nào đó khi tối ưu lợi ích một đoạn nào đó chúng ta đã sai không tối ưu lợi ích tổng thể, như trong lý thuyết trò chơi. Liệu có trường hợp nào mà thuật toán trên bị suy biến ??
Thực ra nghĩ ngợi một lúc đến giờ tôi vẫn không thể tính toán được tính đúng sai giải pháp của mình.
Sau một hồi suy nghĩ tiếp thử các trường hợp thì không hoàn toàn thấy vấn đề với cách làm thung lũng rồi đến đỉnh của mình, tôi bỏ cuộc chứng minh tính đúng sai. Nhưng vẫn còn có thể một giải pháp khác.
Giải pháp này có vẻ thô bạo hơn, quan điểm là, tôi sẽ bán khi ngày mai cao hơn ngày hôm trước, đơn giản thế thôi.
Vâng, và nó lại AC, nếu để ý kỹ lại, nó chính là một phiên bản tốt hơn (bởi ngắn hơn) của giải pháp 2, nhưng tư tưởng không khác gì mấy. Bởi khi đã tìm được vị trí của thung lũng, thay vì đi tìm đỉnh cao nhất gần cái thung lũng đó, ta lại bò từ từ đến cái đỉnh cao nhất đó, trên đường đi ta bán ra, cuối cùng ta lại đến cái đỉnh cao nhất. Lại quay về cách 1. Tôi nghĩ bài toán này sẽ không chỉ dừng lại ở đây, đón chờ xem Leetcode sẽ ra đề gì tiếp theo.
Hết rồi, hẹn gặp Leetcode vào ngày mai.
Đề bài rất là hay đúng không.
Điểm không thực tế của bài toán này đó là tại sao nó không được áp dụng trong kinh tế bởi vì đơn giản nó chỉ thống kê dữ liệu trong quá khứ rồi tối ưu, chứ không có một thuật toán tiên đoán lợi nhuận gì phức tạp cả, nhưng làm tốt bài toán này, ta có thể dễ dàng hình dung tốt hơn về thị trường đầu tư.
Với ví dụ 1, danh sách [7,1,5,3,6,4], khá là khó hình dung, ta sẽ thử vẽ nó bằng biểu đồ:
Ta có nhận xét, thời điểm ta sẽ giao dịch sẽ là thời điểm mà số liệu đang nằm ở vị trí thung lũng (1) (3), hoặc đang ở vị trí đỉnh (5) (6). Bởi sau thung lũng sẽ là đỉnh mà sau đỉnh thì là thung lũng.
Như thế có một giải pháp ở đây là lợi nhuận tối đa ta thu được sẽ bằng hiệu của điểm cao nhất trừ điểm thấp nhất trong 1 khoảng thời gian nào đó.
Dù đã Apcept trên Leetcode, nhưng tôi thấy hình như thuật toán này có vấn đề ?
Liệu có trường hợp nào đó khi tối ưu lợi ích một đoạn nào đó chúng ta đã sai không tối ưu lợi ích tổng thể, như trong lý thuyết trò chơi. Liệu có trường hợp nào mà thuật toán trên bị suy biến ??
Thực ra nghĩ ngợi một lúc đến giờ tôi vẫn không thể tính toán được tính đúng sai giải pháp của mình.
Sau một hồi suy nghĩ tiếp thử các trường hợp thì không hoàn toàn thấy vấn đề với cách làm thung lũng rồi đến đỉnh của mình, tôi bỏ cuộc chứng minh tính đúng sai. Nhưng vẫn còn có thể một giải pháp khác.
Giải pháp này có vẻ thô bạo hơn, quan điểm là, tôi sẽ bán khi ngày mai cao hơn ngày hôm trước, đơn giản thế thôi.
Vâng, và nó lại AC, nếu để ý kỹ lại, nó chính là một phiên bản tốt hơn (bởi ngắn hơn) của giải pháp 2, nhưng tư tưởng không khác gì mấy. Bởi khi đã tìm được vị trí của thung lũng, thay vì đi tìm đỉnh cao nhất gần cái thung lũng đó, ta lại bò từ từ đến cái đỉnh cao nhất đó, trên đường đi ta bán ra, cuối cùng ta lại đến cái đỉnh cao nhất. Lại quay về cách 1. Tôi nghĩ bài toán này sẽ không chỉ dừng lại ở đây, đón chờ xem Leetcode sẽ ra đề gì tiếp theo.
Hết rồi, hẹn gặp Leetcode vào ngày mai.
hay quá
Trả lờiXóa