# leetcode Best Time to Buy and Sell Stock

• 121 Best Time to Buy and Sell Stock
• 122 Best Time to Buy and Sell Stock II
• 123 Best Time to Buy and Sell Stock III
• 188 Best Time to Buy and Sell Stock IV
• 714. Best Time to Buy and Sell Stock with Transaction Fee

### 121 Best Time to Buy and Sell Stock

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 (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

### 122 Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

### 123 Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

nax_price为最大售价，每次减去price[i]得到第i天之后的利润，加上dp[i – 1]即为两次买卖的值。

C++

Python

### 188. Best Time to Buy and Sell Stock IV

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

• dp[i][x] = max(dp[i-1][x] , dp[j][x – 1] + prices[i] – prices[j])  0 <= j < i
• 上面的状态转移方程第一项为第i天不进行交易，第二项为枚举j 从0~i-1，第j天买入，第i天卖出

C++

dp,设dp[i][j]为第J天进行第i次交易能获取的最大值。

• 当k >=n/2时候，相当于第122题。Best Time to Buy and Sell Stock II
• dp[i][j]=max(dp[i][j-1],prices[j] + maxTemp)  我们能获取的最大利润，当我们在第j天进行抛售时。由于maxTemp已经算了买进时的价格，所以直接加上即可。
• maxTemp =max(maxTemp,dp[i-1][j-1] – prices[j])  可以理解为已获得的最大利润，即如果买进第j天的，那么用之前一轮的买卖，前一天的的利润即（dp[i-1][j-1]）减去prices[j]

### 714. Best Time to Buy and Sell Stock with Transaction Fee

Your are given an array of integers `prices`, for which the `i`-th element is the price of a given stock on day `i`; and a non-negative integer `fee` representing a transaction fee.

You may complete as many transactions as you like, but you need to pay the transaction fee for each transaction. You may not buy more than 1 share of a stock at a time (ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:

Note:

• `0 < prices.length <= 50000`.
• `0 < prices[i] < 50000`.
• `0 <= fee < 50000`.

• sell = max(sell, buy + prices[i] – fee)

C++

Java

Python

Leetcode , , , , . permalink.

### One thought on “leetcode Best Time to Buy and Sell Stock”

1. haiyan Pang says:

188. 的第一种解法中，dp[i][x] = max(dp[i][x], dp[j][x – 1] + prices[i] – prices[j]);
是不是应该写成 dp[i][x] = max(dp[i][x], dp[j-1][x – 1] + prices[i] – prices[j]);（j==0的情况要单独处理下），因为如果prices[j] 参与第x次 交易，那么就不能参与之前的交易了
测试表明两种写法结果一致，但还没证明出来为何