算法之股票交易问题
股票购买
交易一次
解法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) {
if (prices == null || prices.length < 2) {
return 0;
}
int len = prices.length;
//dp[i][0] -> 今日不持股的最大利润。 dp[i][1]今日持股的最大利润
//dp[i][0] 对于有两种情况。 1、昨日不持股，则利润为昨日不持股。 2、昨日持股，则今日卖掉了 dp[i][0] = dp[i - 1][0] + prices[i];
int[] dp = new int[2];
//初始化。最开始持股，则利润为 --prices[i]
dp[0] = 0;
dp[1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]);
dp[1] = Math.max(dp[1], -prices[i]);//注意dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);代表能进行多次的买卖。
}
return dp[0];//最终不持股。
} 不限交易次数
解法1: 贪心算法
//贪心算法。 以买入情况下，后一位元素小于当前元素/无后一位元素 卖出。
//以卖出情况下，后一位元素大于当前元素 买入。
public int maxProfit(int[] prices) {
int len = prices.length;
// 特殊判断
if (len < 2) {
return 0;
}
boolean state = false;//代表卖出状态 true 代表买入状态。
int profit = 0;
for (int i = 0; i < len; i++) {
if (!state && i + 1 < len && prices[i + 1] > prices[i]) {
profit -= prices[i];
state = true;
} else if (state && (i + 1 >= len || prices[i + 1] < prices[i])) {
profit += prices[i];
state = false;
}
}
return profit;
}
public int maxProfit(int[] prices) {
int len = prices.length;
// 特殊判断
if (len < 2) {
return 0;
}
int buy = prices[0];//最低购入价
int profit = 0;
for (int i = 1; i < len; i++) {
if (prices[i] < buy) {
buy = prices[i];
} else if (prices[i] > buy){
profit += prices[i] - buy;
buy = prices[i];//更新购入最低价。
}
}
return profit;
} 解法2：动态规划
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int len = prices.length;
//dp[i][0] -> 今日不持股的最大利润。 dp[i][1]今日持股的最大利润
//dp[i][0] 对于有两种情况。 1、昨日不持股，则利润为昨日不持股。 2、昨日持股，则今日卖掉了 dp[i][0] = dp[i - 1][0] + prices[i];
int[] dp = new int[2];
//初始化。最开始持股，则利润为 --prices[i]
dp[0] = 0;
dp[1] = -prices[0];
for (int i = 1; i < len; i++) {
dp[0] = Math.max(dp[0], dp[1] + prices[i]);
dp[1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return dp[0];//最终不持股。
} 交易存在冻结期（1天）- 309
冻结期为k天怎么办？
动态规划
sell[i]表示截至第i天，最后一个操作是卖时的最大收益；
buy[i]表示截至第i天，最后一个操作是买时的最大收益；
cool[i]表示截至第i天，最后一个操作是冷冻期时的最大收益；
递推公式：
sell[i] = max(buy[i-1]+prices[i], sell[i-1]) (第一项表示第i天卖出，第二项表示第i天冷冻)
buy[i] = max(cool[i-1]-prices[i], buy[i-1]) （第一项表示第i天买进，第二项表示第i天冷冻）
cool[i] = max(sell[i-1], cool[i-1])
public int maxProfit(int[] prices) {
int len = prices.length;
//特判
if (len < 2) {
return 0;
}
//buy[i]、sell[i]、cooled[i]表示第 i 天 最后一个操作 是买、卖、冻结能获得的最大利润
int[] buy = new int[len];
int[] sell = new int[len];
int[] cooled = new int[len];
buy[0] = -prices[0];
for (int i = 1; i < len; i++) {
cooled[i] = Math.max(cooled[i - 1], sell[i - 1]);//保持状态(无操作)cooled[i - 1] or 进入冻结;
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);//无操作，或昨日购入今日售出。
buy[i] = Math.max(buy[i - 1], cooled[i - 1] - prices[i]);//无操作 或 进入买入
}
return Math.max(cooled[len - 1], sell[len - 1]);
} 改进写法
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) {
return 0;
}
//由于可以无限次交易，所以只定义两个维度，第一个维度是天数，第二个维度表示是否持有股票，0表示不持有，1表示持有，2表示过渡期
int[][] dp = new int[prices.length][3];
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0;
for (int i = 1; i < prices.length; i++) {
//第i天不持有股票的情况有两种
//a.第i-1天也不持有股票
//b.第i-1天是过渡期
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][2]);
//第i天持有股票有两种情况
//a.第i-1天也持有股票，第i天不操作，
//b.第i-1天不持有股票，在第i天买入
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]);
//第i天是冷冻期只有一种情况，第i-1天持有股票且卖出
dp[i][2] = dp[i-1][1] + prices[i];
}
//最后最大利润为最后一天，不持有股票或者进入冷冻期的情况
return Math.max(dp[prices.length-1][0], dp[prices.length-1][2]);
} 交易存在手续费
解法1：贪心算法，购入时付手续费。
当前价格小于购入价格，则更新购入价格
当前价格大于购入价格，则利润更新， 更新购入价格（例如此时是i天卖出，则购入价格最低为 i天价格），注意更新的价格，防止递增数列。；
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
// 特殊判断
if (len < 2) {
return 0;
}
int buy = prices[0] + fee;
int profit = 0;
for (int i = 1; i < len; i++) {
if (prices[i] + fee < buy) {//存在更小的购入价格。
buy = prices[i] + fee;
} else if (prices[i] > buy) {//有利润
profit += prices[i] - buy;
buy = prices[i];//更新购入价格，当前能购入的最低价格。 注意此处是 prices[i] 而不是prices[i] + fee, 因此若是递增，则会付多次手续费用。
}
}
return profit;
} 解法2：动态规划
public int maxProfit(int[] prices, int fee) {
int len = prices.length;
// 特殊判断
if (len < 2) {
return 0;
}
int[][][] dp = new int[len][2][2];
dp[0][0][0] = -prices[0];
dp[1][1][]
} 最多完成2次交易
动态规划：
注意初始条件：
其实第一天的dp[2]、dp[3]和dp[4]是无意义的，也不需要初始化。
真正需要初始化的是：
第二天的dp[2]：第二天及之后才能第一次卖
第三天的dp[3]：第三天及之后才能第二次买
第四天的dp[4]：第四天及之后才能第二次卖
此外在循环过程中需要进行天数的判断
dp[i][0] -> 无买入卖出
dp[i][1] -> 第一次买入
dp[i][2] -> 第一次买入
dp[i][3] -> 第二次买入
dp[i][4] -> 第二次买入 public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2) {
return 0;
}
int n = prices.length;
int[][] dp = new int[n][5];
dp[0][0] = 0;//第一天不动
// 第一天 第一次买
dp[0][1] = -prices[0];
// 第二天 第一次卖
dp[1][2] = dp[0][1] + prices[1];
// 第三天 第二次买
if (n > 2) {
dp[2][3] = dp[1][2] - prices[2];
}
// 第四天 第二次卖卖
if (n > 3) {
dp[3][4] = dp[2][3] + prices[3];
}
for (int i = 1; i < n; i++) {
// 初始状态其实都是0，写出来只是为了便于理解状态转换
dp[i][0] = dp[i - 1][0];
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
// 第二天及之后才能第一次卖，第二天作为初始情况已在循环外初始化，因此此处处理第二天之后
if (i > 1) {
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
}
dp[i][2] = i == 1 ? dp[0][1] + prices[i] : Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
// 第三天及之后才能第二次买，第三天作为初始情况已在循环外初始化，因此此处处理第三天之后
if (i > 2) {
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
}
// 第四天及之后才能第二次卖，第四天作为初始情况已在循环外初始化，因此此处处理第四天之后
if (i > 3) {
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
}
// 持有股票状态必不可能获得最大收益（只买不卖），所以不用考虑持有状态
return Math.max(Math.max(dp[n - 1][0], dp[n - 1][2]), dp[n - 1][4]);
} - 递归 + 记忆体
//state = 1代表买入状态。
//state = 0代表卖出状态。
Map<Key,Integer> map;
public int maxProfit(int[] prices) {
if(prices==null || prices.length==0) {
return 0;
}
int n = prices.length;
//用一个哈希表缓存重复的调用
map = new HashMap<Key,Integer>();
return dfs1(prices,0,0,0);
}
private int dfs1(int[] prices,int index,int status,int k) {
Key key = new Key(index,status,k);
//已存在，之间调用
if(map.containsKey(key)) {
return map.get(key);
}
//终止条件。
if(index==prices.length || k==2) {
return 0;
}
int still=0,sell=0,buy=0;
still = dfs1(prices,index+1,status,k);//无操作。
if(status==1) {
//卖出
sell = dfs1(prices,index+1,0,k+1)+prices[index];
}
else {
//买入
buy= dfs1(prices,index+1,1,k)-prices[index];
}
//获得三种操作的最大收益。
map.put(key, Math.max(Math.max(a,b),c) );
return map.get(key);
}
//Key对象封装了index、status、交易次数，作为map的key 或者将其序列化
private class Key {
final int index;
final int status;
final int k;
Key(int index,int status,int k) {
this.index = index;
this.status = status;
this.k = k;
}
//这里需要实现自定义的equals和hashCode函数
public int hashCode() {
return this.index * 3 + this.status * 5 + this.k * 7;
}
public boolean equals(Object obj) {
Key other = (Key)obj;
if(index==other.index && status==other.status && k==other.k) {
return true;
}
return false;
}
} 最多k次交易
- 当len / 2小于k，等同于无限次操作。
- 否则代表有限次操作 -> 递归 + 记忆体。
投递美团等公司10个岗位
