# 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];
    }
}
```