# 121.Buy And Sell Stock

九月 22, 2021

### Description:

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:**

1 | Input: prices = [7,1,5,3,6,4] |

### Brute Force:

Traverse all price pairs, ans = max(ans,pair[j]-pair[i]), where j > i.

Steps:$n^2/2$ -> TLE

### Note:

#### Define:

Max_profit = max{price[j]-price[i]}

0<= i < j < n-1

#### Finding:

Buy: price[i] = min{prices[:i]}

Sell: price[j] = max{prices[j:]}

### Solution:

#### 1.Keep track of the minimun price so far:

1 | Traverse the price: |

#### 2.Convert the priceList to the gainList

Example:

prices = [7,1,5,3,6,4]

Gains = [0,-6,4,-2,3,-2]

### Note:

The profit is the sum of a subarray in gains.

And the max_profit = the largest sum of subarray of an array(LeetCode 53).

#### Using Kadane’s Algorithm

1 | class Solution: |

加载评论