Giải thích và mã giả:

Để giải quyết vấn đề này, trước tiên người ta sử dụng một Cách tiếp cận thuật toán Brute Force. chúng tôi sẽ thử tất cả lợi nhuận có thể có được từ các giá trị nhất định và chọn giá trị cao nhất. Để tính lợi nhuận tối đa bạn có thể đạt được từ mỗi giao dịch.

• Tạo một biến maxProfit để lưu trữ lợi nhuận tối đa
• Lặp lại mảng hai lần để có được giá mua và giá bán
• Tính lợi nhuận bằng cách trừ đi buyPrice từ sellPrice
• Nếu lợi nhuận giá trị lớn hơn giá trị lợi nhuận tối đa giá trị, đặt maxProfit bằng lợi nhuận
• trở lại maxProfit

Phân tích độ phức tạp

• Độ phức tạp về thời gian: O(n²) trong đó n là độ dài của mảng giá
• Độ phức tạp của không gian: O(1). chỉ có hai biến được tạo ra. maxLợi nhuận và lợi nhuận

Cách tiếp cận tốt hơn bằng cách sử dụng One For Loop;

từ phần giải thích ở trên, bạn sẽ nhận thấy có một mô hình được sử dụng để tính lợi nhuận tối đa. Thay vì phải tính toán lại tất cả các giá trị với nhau, chúng ta có thể theo dõi giá tối thiểu và trừ nó khỏi giá bán như sau

Giải thích và mã giả:

• tạo một biến để lưu trữ giá tối đa
• tạo một biến khác để theo dõi giá tối thiểu và đặt nó thành giá trị đầu tiên trong mảng
• lặp qua mảng giá bắt đầu từ chỉ số 1 làm giá bán của bạn
• để có được lợi nhuận, bạn trừ đi minPrice từ giá bán
• Nếu lợi nhuận lớn hơn lợi nhuận tối đa, hãy thay thế giá trị MaxProfit bằng giá trị lợi nhuận

mặt khác để tính lợi nhuận cho các giá trị khác, hãy kiểm tra xem giá trị hiện tại có phải là giá trị không bánGiá nhỏ hơn minPrice giá trị. Nếu đúng như vậy, hãy đặt giá trị hiện tại là giá bán cho minPrice.

• trả lại lợi nhuận tối đa

Dưới đây là bảng phân tích cách mã tính toán và trả về lợi nhuận tối đa bằng cách sử dụng một vòng lặp for;

Phân tích độ phức tạp

• Độ phức tạp về thời gian: O(n) trong đó n là độ dài của mảng giá
• Độ phức tạp của không gian: O(1). chỉ có hai biến được tạo ra. maxProfit và minPrice