# 121. Best Time to Buy and Sell Stock.js

找一個陣列裡的最大最小值，可以先設 min = Number.MAX_SAFE_INTEGER，max = Number.MIN_SAFE_INTEGER

LeetCode

Say you have an array for which the ith 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.

Note that you cannot sell a stock before you buy one.

input: 一組陣列代表某一個股票在七天內的價錢
output: 算出哪天賣最劃算 (一定要先買再賣)

Example 1:

Input: [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.
             Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
*/

/**
 * @param {number[]} prices
 * @return {number}
 */
var maxProfit = function(prices) {}

怎麼解

這題用 DP 會比較簡單，總共會有兩種方式一個是 hold 一種是 sell

dp = Array.from({length: n}, () ⇒ Array(2).fill(0))

• hold (dp[i][0]): 之前就買的成本 vs 現在買的成本 選低的

• sell(dp[i][1]): 現在賣 vs 之前賣 選高的

dp[i][0] = Math.max(
            dp[i-1][0],    // Keep holding from yesterday
            -prices[i]     // Buy today (only allowed one transaction)
        );
        
        // For not holding stock on day i:
        dp[i][1] = Math.max(
            dp[i-1][1],              // Stay without stock
            dp[i-1][0] + prices[i]   // Sell today
        );

function maxProfitDP(prices) {
    const n = prices.length;
    if (n <= 1) return 0;
    
    // Create a 2D array: dp[day][state]
    // state 0 = holding stock, state 1 = not holding stock
    const dp = Array(n).fill(0).map(() => Array(2).fill(0));
    
    // Day 0: Base case
    dp[0][0] = -prices[0]; // If we buy on day 0, profit = -price
    dp[0][1] = 0;          // If we don't buy, profit = 0
    
    // Fill the table day by day
    for (let i = 1; i < n; i++) {
        // For holding stock on day i:
        dp[i][0] = Math.max(
            dp[i-1][0],    // Keep holding from yesterday
            -prices[i]     // Buy today (only allowed one transaction)
        );
        
        // For not holding stock on day i:
        dp[i][1] = Math.max(
            dp[i-1][1],              // Stay without stock
            dp[i-1][0] + prices[i]   // Sell today
        );
    }
    
    // Return the best profit when we don't hold stock at the end
    return dp[n-1][1];
}

or

export default function optimalStockTrading(prices) {
  let len = prices.length
  if(len < 2) return 0
  let dp =  Array.from({length: len}, () => Array(2).fill(0))
  dp[0][1] = prices[0]
  /*
  dp[i][0] sold: 現在賣跟之前賣選高
  dp[i][1] hold: 現在買過之前買選低
  */
  for(let i=1; i<len; i++){
    dp[i][1] = Math.min( prices[i], dp[i-1][1])
    dp[i][0] = Math.max( prices[i] - dp[i-1][1], dp[i-1][0])
  }


  return dp[len-1][0]
}

```javascript
var maxProfit = function(prices) {
    let profit = 0;
    let lowPrice = prices[0];

    for(let i=1; i<prices.length; i++){
        if((prices[i] - lowPrice) > profit){
            profit = prices[i] - lowPrice
        }
        if(prices[i] < lowPrice){
            lowPrice = prices[i]
        }
       
    }

    return profit;
};
```

學到什麼

比最大最小值，可以先從以下開始

min = Number.MAX_SAFE_INTEGER or 0 
max = Number.MIN_SAFE_INTEGER or 0