官方地址
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。股票问题系列思路
121 最多买入和卖出一支股票一次
122 无数次
123 2次，同时只能持有一支股票
309 有冷却时间
188 最多 k 次交易
714 有交易手续费一个方法团灭六个股票问题
dp[i][k][0 or 1] (0 <= i <= n-1, 1 <= k <= K)
- i 为天数，到第 i 天的最大利润
- k 为最多交易次数
- [0,1] 为是否持有股票
总状态数: n K 2 种状态
for 0 <= i < n:
for 1 <= k <= K:
for s in {0, 1}:
dp[i][k][s] = max(buy, sell, rest)
股票买卖
时间复杂度 O(N K) 时间复杂度 O(N K)
如果可以持有 X 股份 则 复杂度为 O(N K X)
# max( 选择 rest , 选择 sell)
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
解释:今天我没有持有股票，有两种可能:
- 我昨天就没有持有，然后今天选择 rest，所以我今天还是没有持有;
- 我昨天持有股票，但是今天我 sell 了，所以我今天没有持有股票了。
# max( 选择 rest , 选择 buy)
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])
解释: 今天我持有着股票，有两种可能:
- 我昨天就持有着股票，然后今天选择 rest，所以我今天还持有着股票;
- 我昨天本没有持有，但今天我选择 buy，所以今天我就持有股票了。
初始状态:
dp[-1][k][0] = dp[i][0][0] = 0
dp[-1][k][1] = dp[i][0][1] = -infinity
状态转移方程:
dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - prices[i])
结果为:
Math.max(dp[n-1][0...k][0])解法一
暴力解法
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for(int i = 0; i < prices.length; i++) {
int one = prices[i];
for(int j = i+1;j < prices.length; j++) {
int profit = prices[j] - prices[i];
max = Math.max(profit, max);
}
}
return max;
}
}
解法二
贪心
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < prices[i + 1]) max = prices[i+1] - prices[i]; // 只要后一天比前一天股价高，就买入
}
return max;
}
}
解法三
动态规划
class Solution {
public int maxProfit(int[] prices) {
int minPrice = Integer.MAX_VALUE;
int max = 0;
for(int i = 0; i < prices.length; i++) {
int price = prices[i];
if (minPrice > prices[i]) {
minPrice = prices[i];
}
max = Math.max(max, prices[i] - minPrice);
}
return max;
}
}
class Solution {
public int maxProfit(int[] prices){
if (prices == null || prices.length == 0) return 0;
int result = 0;
int[][] profit = new int[prices.length][3];
profit[0][0] = 0; // 0 表示没有买入股票
profit[0][1] = -prices[0]; // 1 表示买入了一股股票还没有卖
profit[0][2] = 0; // 2 表示之前买了一股股票，第 i 天卖掉了
for (int i = 1; i < prices.length; i++) {
profit[i][0] = profit[i - 1][0]; // 第 i 天不持有股票，第 i 天也不买入股票，那么最大利润 就是前一天没有持有股票的状态
profit[i][1] = Math.max(profit[i - 1][1], profit[i - 1][0] - prices[i]); //第 i 天持有股票，分两种情况， 第一种是之前买了一股，第二种是第 i 天买了一股
profit[i][2] = profit[i - 1][1] + prices[i]; // 第 i 天持有股票，这支股票是之前买的，并且当天要套现
result = Math.max(result, profit[i][0]);
result = Math.max(result, profit[i][1]);
result = Math.max(result, profit[i][2]);
}
return result;
}
}
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if not prices: return 0
res = 0
profit = [[0 for i in range(3)] for i in range(len(prices))]
profit[0][0], profit[0][1], profit[0][2] = 0, -prices[0], 0
for i in range(1, len(prices)):
profit[i][0] = profit[i - 1][0]
profit[i][1] = max(profit[i - 1][1], profit[i - 1][0] - prices[i])
profit[i][2] = profit[i - 1][1] + prices[i]
res = max(res, profit[i][0], profit[i][1], profit[i][2])
return res