Best Time to Buy and Sell Stock

🏠 ⬅️ ➡️

You are given an array prices where prices[i] is the price of a given stock on the ith day.

You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.

Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4] Output: 5 Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5. Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.

Example 2:

Input: prices = [7,6,4,3,1] Output: 0 Explanation: In this case, no transactions are done and the max profit = 0.

Constraints:

  • 1 <= prices.length <= 105
  • 0 <= prices[i] <= 104
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 7
    integer, dimension(n) :: prices
    integer :: i
    integer :: result

    ! Example 1
    prices = (/ 7, 1, 5, 3, 6, 4 /)
    write (*, '(A)') 'Example 1'
    result = max_profit(prices)
    write (*, '(A, I0)') 'Max profit: ', result

    ! Example 2
    prices = (/ 7, 6, 4, 3, 1 /)
    write (*, '(A)') 'Example 2'
    result = max_profit(prices)
    write (*, '(A, I0)') 'Max profit: ', result

contains

    function max_profit(prices) result(max_profit_)
        implicit none
        integer, dimension(:), intent(in) :: prices
        integer :: max_profit_
        integer :: min_price
        integer :: max_price
        integer :: i

        min_price = prices(1)
        max_price = prices(1)
        max_profit_ = 0

        do i = 2, size(prices)
            if (prices(i) < min_price) then
                min_price = prices(i)
            else if (prices(i) > max_price) then
                max_price = prices(i)
            end if
        end do

        if (max_price > min_price) then
            max_profit_ = max_price - min_price
        end if
    end function max_profit
end program main
❌ Compiled
❌ Executed
❌ Correct 
module max_profit
implicit none
private
public :: max_profit_func

contains

function max_profit_func(prices) result(max_profit)
integer, intent(in) :: prices(:)
integer :: max_profit, buy_price, sell_price, i

! Initialize variables
max_profit = 0
buy_price = 0
sell_price = 0

! Loop through the prices array
do i = 2, size(prices)
    ! If the current price is greater than the buy price,
    ! then update the buy price
    if (prices(i) > buy_price) then
        buy_price = prices(i)
    end if

    ! If the current price is less than the sell price,
    ! then update the sell price
    if (prices(i) < sell_price) then
        sell_price = prices(i)
    end if
end do

! Calculate the maximum profit
max_profit = sell_price - buy_price

end function max_profit_func
end module max_profit

! Test the max_profit function with the provided examples
program test_max_profit
use max_profit
implicit none
integer :: prices(6)
integer :: max_profit

! Example 1
prices = [7, 1, 5, 3, 6, 4]
max_profit = max_profit_func(prices)
write (*,*) "Example 1: Max profit = ", max_profit

! Example 2
prices = [7, 6, 4, 3, 1]
max_profit = max_profit_func(prices)
write (*,*) "Example 2: Max profit = ", max_profit

end program test_max_profit
🌐 Data from online sources 
def maxProfit(prices):
    minPrice = float('inf')
    maxProfit = 0
    for price in prices:
        minPrice = min(minPrice, price)
        maxProfit = max(maxProfit, price - minPrice)
    return maxProfit

The algorithm iterates through the input array of prices. We maintain two variables: minPrice to track the minimum price encountered up to the current day, and maxProfit to track maximum achievable profit.

For each day, we update: 1. minPrice by comparing its value with the current day's stock price. 2. maxProfit by comparing its value with the difference between the current day's stock price and the minimum stock price encountered so far.

At the end of the iteration, the algorithm returns the value stored in maxProfit, which is the maximum possible profit that can be achieved.

🌐 Data from online sources 
int maxProfit(vector<int>& prices) {
    int minPrice = INT_MAX;
    int maxProfit = 0;
    for (int price : prices) {
        minPrice = min(minPrice, price);
        maxProfit = max(maxProfit, price - minPrice);
    }
    return maxProfit;
}

The algorithm iterates through the input array of prices. We maintain two variables: minPrice to track the minimum price encountered up to the current day, and maxProfit to track maximum achievable profit.

For each day, we update: 1. minPrice by comparing its value with the current day's stock price. 2. maxProfit by comparing its value with the difference between the current day's stock price and the minimum stock price encountered so far.

At the end of the iteration, the algorithm returns the value stored in maxProfit, which is the maximum possible profit that can be achieved.