# 买卖股票

• 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
• 309 Best Time to Buy and Sell Stock with Cooldown

## 121. Best Time to Buy and Sell Stock

Problem:

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.

Example 1:

Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 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 In this case, no transaction is done, i.e. max profit = 0.

### 思路1

```    public int maxProfit(int[] prices) {
int minprice = Integer.MAX_VALUE;
int maxprofit = 0;
for (int i =0;i<prices.length;i++){
if (prices[i] < minprice){
minprice = prices[i];
}else if (prices[i]-minprice > maxprofit){
maxprofit = prices[i] - minprice;
}
}
return maxprofit;
}```

### 思路2

```    public int maxProfit(int[] prices) {

int sell = 0;

for (int price : prices){
sell = Math.max(sell, buy + price);
}

return sell;
}```

### 思路3

```public int maxProfit(int[] prices) {
int sum = 0;
int max = 0;

for (int i = 1; i < prices.length;i++){
sum = Math.max(0, sum += prices[i]-prices[i-1]);
max = Math.max(max, sum);
}

return max;
}```

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

Problem:

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).

```    public int maxProfit(int[] prices) {
int max = 0;
for (int i = 0; i < prices.length -1; i++){
if (prices[i+1] > prices[i]) max += prices[i+1] - prices[i];
}
return max;
}```

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

Problem:

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).

``` public int maxProfit(int[] prices) {
int sell1 = 0, sell2 = 0, buy1 = Integer.MIN_VALUE, buy2 = Integer.MIN_VALUE;
for (int i = 0; i < prices.length; i++) {
sell1 = Math.max(sell1, buy1 + prices[i]);
sell2 = Math.max(sell2, buy2 + prices[i]);
}
return sell2;
}```

`buy1 = Math.max(buy1, 0 - prices[i]);`

`sell1 = Math.max(sell1, buy1 + prices[i]);`

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

Problem:

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).

```public int maxProfit(int k, int[] prices) {

if (k == 0) return 0;

if (k >=  prices.length/2) {
int maxPro = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] > prices[i-1])
maxPro += prices[i] - prices[i-1];
}
return maxPro;
}

int[] sell = new int[k];

for (int i = 0; i < prices.length;i++){
for (int j = 1; j < k; j++){
}
}
return sell[k-1];
}```

## 309. Best Time to Buy and Sell Stock with Cooldown

Problem:

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) with the following restrictions: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2] maxProfit = 3 transactions = [buy, sell, cooldown, buy, sell]

```buy[i]  = max(rest[i-1]-price, buy[i-1])

```public int maxProfit(int[] prices) {

int n = prices.length;

int[] sell = new int[n+1];
int[] rest = new int[n+1];

sell[0] = rest[0] = 0;

for (int i = 0; i < n; i++) {

sell[i+1] = Math.max(buy[i] + prices[i], sell[i]);
}

return sell[n];
}```

0 条评论

• ### LWC 73: 789. Escape The Ghosts

思路： 最优策略：所有ghost都守候在target处，等你来。所以只要计算ghost的曼哈顿距离中最小的，与你到target处的距离进行比较即可。可参考证...

• ### 挑战程序竞赛系列（77）：4.3 2-SAT（1）

挑战程序竞赛系列（77）：4.3 2-SAT（1） 传送门：POJ 3683: Priest John’s Busiest Day 题意： 有n个婚礼，每个...

• ### LWC 58：724. Find Pivot Index

LWC 58：724. Find Pivot Index 传送门：724. Find Pivot Index Problem: Given an array ...

• ### Leetcode 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 o...

• ### NOIP训练营内部试题-数数（树形DP+倍增）

样例读入： 4 1 2 1 3 2 4 样例输出： 8 样例解释：

• ### LOJ#6283. 数列分块入门 7

内存限制：256 MiB时间限制：500 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： hzwer 提交提交记录统计讨论测试数据 题目描述 给出...

• ### 09年8月9日 ECUST ACM 练习赛总结

B题补充: B题的DP方法比较诡异(起码我理解了很久) 令fn[i][j]为有i个数j次交换位置的排列数量 很明显,当i+1时,如果把新增的数放在最后一位...

• ### LOJ#6280. 数列分块入门 4

内存限制：256 MiB时间限制：500 ms标准输入输出 题目类型：传统评测方式：文本比较 上传者： hzwer 提交提交记录统计讨论测试数据 题目描述 给出...