股票买卖
股票买卖
简单买卖: 只允许买卖一次
本题意思就是你得到一系列在接下来几天的股票价格，现在你被允许只用一次交易
/**
* @function 仅允许买卖一次
* @description 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.
* @OJ https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
*/
public class Stock1 {
public int maxProfit(int[] prices) {
//存储最大值的变量,初始化为0
int ans = 0;
//判断是否有效价格序列
if (prices.length == 0) {
return ans;
}
//判断应该在哪一日买入,即最小值
int bought = prices[0];
//遍历所有交易日价格
for (int i = 1; i < prices.length; i++) {
//判断本日是否能够卖出
if (prices[i] > bought) {
//判断如果本日卖出收益是否最大
if (ans < (prices[i] - bought)) {
ans = prices[i] - bought;
}
} else {
//判断本日是否为最低价格
bought = prices[i];
}
}
return ans;
}
}
简单买卖: 可以买卖无穷多次
意思是买卖股票时可以不计买卖次数，但是必须在买之前先把以前的股票卖掉。然后求能获利最大的额度。这样的话也很简单，只要遇见下一天的价格比这一天价格高的话，就卖出。代码如下：
/**
* 能够进行无穷多次买卖, 求取最大值
*/
public class Stock2 {
public int maxProfit(int[] prices) {
int total = 0;
//遍历所有交易日
for (int i = 0; i < prices.length - 1; i++) {
//只要是后一天比前一天贵,就卖出
if (prices[i + 1] > prices[i]) total += prices[i + 1] - prices[i];
}
return total;
}
}
最多买卖两次
现在你被允许买卖的次数减少到最多交易两次，也是必须先卖出再买进。然后求能获利的最大额度。我们来琢磨一下这个规则，每次交易必须先卖掉手上这只股票才能进行下次操作，比如下面几天的股票价格为，买第一只股票价格为
/**
* 最多两次买卖
* @OJ https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
*/
public class Stock3 {
public static int maxProfit(int[] prices) {
//判断是否为有效交易天数
if (prices.length == 0) return 0;
//存放左半部分最大收益
int[] left = new int[prices.length];
//存放右半部分最大收益
int[] right = new int[prices.length];
//初始化为0
int leftMin = prices[0];
int rightMax = prices[prices.length - 1];
//总收益
int sum = 0;
//计算左半段最大收益
for (int i = 1; i < prices.length; i++) {
//获取左半部分的最低价
leftMin = Math.min(prices[i], leftMin);
//获取左半部分最大收益
left[i] = Math.max(prices[i] - leftMin, left[i - 1]);
}
//计算右半段最大收益
for (int i = prices.length - 2; i >= 0; i--) {
//获取右半部分最低价
rightMax = Math.max(prices[i], rightMax);
//获取右半部分最大收益
right[i] = Math.max(rightMax - prices[i], right[i + 1]);
}
// 找出两次交易最大收益组合
for (int i = 0; i < prices.length; i++) {
if ((left[i] + right[i]) > sum) sum = left[i] + right[i];
}
return sum;
}
public static void main(String args[]) {
int[] prices = new int[]{1, 7, 15, 6, 57, 32, 76};
System.out.print("maxProfit is" + maxProfit(prices));
}
}
在上面
最多买卖K 次
此情况下允许用户买卖多次，以期获取最大值。最方便想到的办法会是回溯，不过不可避免的会导致重复计算，因此最好的还是进行动态规划。当我们考虑如何构建动态规划的状态转换函数时，首先假想下我们构建的状态转移表，应该会包含
hold[i][j]: 对于0~i 天中最多进行j 次交易并且第i 天仍然持有股票的收益unhold[i][j]: 对于0~i 天中最多进行j 次交易并且第i 天不持有股票的收益
第
- hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
第
- unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
代码如下
public class Stock4 {
/**
* @param k 可交易的次数
* @param prices 价格向量
* @return
* @function 计算最多K次情况下能获得的最大理论
*/
public int maxProfit(int k, int[] prices) {
if (k == 0 || prices.length < 2)
return 0;
if (k > prices.length / 2)
return noLimit(prices);
// hold[i][j]: 对于0~i天中最多进行j次交易并且第i天仍然持有股票的收益
// unhold[i][j]: 对于0~i天中最多进行j次交易并且第i天不持有股票的收益
// 第 i 天持有股票的收益为 之前买了股票但还没有卖出 或者 今天才选择买入股票 二者中较大值
// hold[i][j] = Math.max(unhold[i-1][j]-prices[i],hold[i-1][j]);
// 第 i 天不持有股票的收益为 选择今天卖出 或者 今天不买入时 最大的收益
// unhold[i][j] = Math.max(hold[i-1][j-1]+prices[i],unhold[i-1][j]);
int[][] hold = new int[k + 1][prices.length];
int[][] unhold = new int[k + 1][prices.length];
for (int i = 1; i <= k; i++) {
//初始化持有状态下的初始值
hold[i][0] = -prices[0];
//初始化不持有状态下的初始值 为0
unhold[i][0] = 0;
for (int j = 1; j < prices.length; j++) {
hold[i][j] = Math.max(-prices[j] + unhold[i - 1][j], hold[i][j - 1]); // Buy or not buy
unhold[i][j] = Math.max(prices[j] + hold[i][j - 1], unhold[i][j - 1]); // Sell or not sell
}
}
//真实情况下最后一天了还是要卖出的
return unhold[k][prices.length - 1];
}
private int noLimit(int[] prices) { // Solution from Best Time to Buy and Sell Stock II
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;
}
}
T+2 规则
本题意为用户在卖出之后需要休息一天才能进行操作，那么在本题中用户是存在有三个状态，未持有
其对应的状态转换函数为
unhold[i] = max(unhold[i - 1], cooldown[i - 1]); // Stay at s0, or rest from s2
hold[i] = max(hold[i - 1], unhold[i - 1] - prices[i]); // Stay at s1, or buy from s0
cooldown[i] = hol[i - 1] + prices[i]; // Only one way from s1
代码为
public class StockWithCoolDown {
public int maxProfit(int[] prices) {
//判断日期长度是否大于1
if (prices.length <= 1) {
return 0;
}
//构建三个状态数组
int[] unhold = new int[prices.length];
int[] hold = new int[prices.length];
int[] cooldown = new int[prices.length];
unhold[0] = 0;
hold[0] = -prices[0];
cooldown[0] = Integer.MIN_VALUE;
for (int i = 1; i < prices.length; i++) {
unhold[i] = Math.max(unhold[i - 1], cooldown[i - 1]);
hold[i] = Math.max(hold[i - 1], unhold[i - 1] - prices[i]);
cooldown[i] = hold[i - 1] + prices[i];
}
return Math.max(unhold[prices.length - 1], cooldown[prices.length - 1]);
}
}