> For the complete documentation index, see [llms.txt](https://ucan.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ucan.gitbook.io/notes/dynamic-programming/121.-best-time-to-buy-and-sell-stock.md).

# 121. Best Time to Buy and Sell Stock

[Say you have an array for which the *i*th element is the price of a given stock on day *i*. If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.](https://leetcode.com/problems/best-time-to-buy-and-sell-stock/)

```java
class Solution {
    public int maxProfit(int[] prices) {
        // set dp[i] = the max profix of subarray start from 0 end at index i
        // int min = the minimal vale of subarray start from 0 end at index i-1
        // dp[i] = Math.max(dp[i-1], prices[i]-min);
        
        if (prices.length<1) return 0;
        
        // initialize the base case
        // for i =0, dp[i]=0
        int min = prices[0];
        prices[0]=0;
        for (int i=1; i<prices.length; i++){
            int temp = prices[i];
            prices[i] = Math.max(prices[i-1], prices[i]-min);
            min = temp<min? temp: min;
        }
        return prices[prices.length-1];
    }
}
```