今日算法之_60_买卖股票的最佳时机
前言
Github:https://github.com/HealerJean
1、买卖股票的最佳时机1
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。
注意:你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
示例 2:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
1.1、解题思路
此题其实很容易,只有明白后面肯定有比前面的大的情况
1.2、算法
public int maxProfit(int prices[]) {
if (prices.length == 0){
return 0;
}
int min = prices[0];
int res = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i] < min) {
min = prices[i];
}
res = Math.max(prices[i] - min, res);
}
return res;
}
1.3、测试
@Test
public void test(){
int[] prices = {7,1,5,3,6,4} ;
System.out.println(maxProfit(prices));
}
2、买卖股票的最佳时机_2
给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易(多次买卖一支股票) 。
注意:你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
2.1、解题思路
有点类似于多数元素
示例 1:
输入: [7,1,5,3,6,4]
输出: 7
解释: 在第 2 天(股票价格 = 1)的时候买入,在第 3 天(股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
随后,在第 4 天(股票价格 = 3)的时候买入,在第 5 天(股票价格 = 6)的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
2.2、算法
public int maxProfit(int prices[]) {
if (prices.length == 0){
return 0;
}
//flag 可以重新买入:true,可以随时买入卖出:false
boolean flag = false ;
int min = prices[0]; //买入的最低价格
int res = 0;
for (int i = 1; i < prices.length; i++) {
//已经卖出了, 此时可以买入了,我们要设置当前最低价格
if (flag){
min = prices[i];
flag = false;
//可以卖出
}else {
//如果当前价格比买入的价格还要低或者相等的时候,设置最低买入价格,i继续向前移动
//我们是要买入,相等的时候,你也不会卖出呀,所以一直到prices[i] 直最后的结果肯定比min大,这样才会
if (prices[i] <= min) {
min = prices[i];
}else {
//min肯定会有值,如果可以买入,
// 并且买入价格是按照比第二条的价格高或者相等的时候会截至,因为你想相等了还可以买入呀,
// 的时候或者是数组最后一个元素的时候,要卖出,否则继续移动i指针
if ((i != prices.length-1) && (prices[i] > prices[i+1]) || i == prices.length-1){
res = res + prices[i] - min;
flag = true;
}
}
}
}
return res;
}
2.3、测试
@Test
public void test(){
int[] prices = {1,2,3,4,5} ;
System.out.println(maxProfit(prices));
}
3、买卖股票的最佳时机_3
给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。
示例 1:
输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。
示例 2:
输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。
示例 3:
输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。
3.1、解题思路
动态规划,具体看算法里面的注释吧,注释很棒的
3.2、算法
public int maxProfit(int[] prices) {
if (prices.length == 0 ) {
return 0;
}
// 初始化
int[][] dp = new int[prices.length][5];
// 3 状态都还没有发生,因此应该赋值为一个不可能的数
for (int i = 0; i < prices.length; i++) {
dp[i][3] = Integer.MIN_VALUE;
}
//卖出的时候,相当于是 卖出价格prices[i] - 前一天的价格,我们何不把买入价格,直接就设置为负数呢。然后负数的买入价格每次取最大的,这样得到的真实买入价格就是小的。利润会最大化
//初始化第一个买入价格price
dp[0][1] = -prices[0];
for (int i = 1; i < prices.length; i++) {
///dp[i][3],第i天,第一次买入后手里还有多少钱 = Math.max(假如入上一天前买入后手里的钱dp[i - 1][1], 当天如果买入股票后手里的钱 -prices[i])
//想象空手套白狼,一开始我们手里就没钱,初始钱就是0,,
// 现在我们是追求利益最大化,谁都想买在低点,买股票肯定是买价格低的。只有买价格低的,后面张了就能挣钱。买在高点,咋地,追涨杀跌呀
// 买了股票之后手里就变成负数了哦 。比如,前一天价格是3 ,今天价格是5 ,那我们肯定不会买5呀,肯定会买3.买了之后,我们手里的钱就是 -3 。所以是Math.max
dp[i][1] = Math.max(dp[i - 1][1], - prices[i]);
//dp[i][2](从头到尾) 第i天,第一次卖出后手里还有多少钱 = Math.max(加入上一天卖出股票后手里的钱 dp[i - 1][2],, 上一天前<不一定非得上一天哦>第一次买入股票后手里的钱 dp[i - 1][1] + 股票当天卖出的价格 prices[i])
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//dp[i][3] 第i天,(第二次买入后现在手里还有多少钱) =Math.max(加入上一天之前买入后手里的钱dp[i-1][3], 当天买入手里的钱(第二次) => 买入(上一天前第一次的盈利dp[i - 1][2]) + (如果当天买入股票需要的钱 - prices[i]))
dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//dp[i][4] 第i天,第二次卖出后现在手里还有多少钱 = Math.max(如果上一天卖出手里的钱dp[i - 1][4], 当天卖出后手里的钱(第二次) =》 上一天前(不一定非得上一天哦)第二次买入股票手里的钱dp[i - 1][3] + 股票当天的价格dp[i - 1][3] + prices[i])
dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
}
//dp[len - 1][2] 最后的结果是从头到尾至买入一次高的收入。肯定不如价格跌下来,继续买入再卖出一次的收入多。
//但是也有可能我们就只能买一次,那就是价格不会跌下来(比如1,2,3,4,5)。 这样的结果就是dp[len - 1][2]了
return Math.max(dp[prices.length - 1][2], dp[prices.length - 1][4]);
}
3.3、测试
@Test
public void test(){
// int[] prices = {3,3,5,0,0,3,1,4} ;
int[] prices = {1,2,3,4,5} ;
System.out.println(maxProfit(prices));
}
4、最佳买卖股票时机含冷冻期
给定一个整数数组,其中第 i 个元素代表了第 i 天的股票价格 。设计一个算法计算出最大利润。在满足以下约束条件下,你可以尽可能地完成更多的交易(多次买卖一支股票):卖出股票后,你无法在第二天买入股票 (即冷冻期为 1 天)。
示例:
输入: [1,2,3,0,2]
输出: 3
解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
4.1、解题思路
动态规划,具体看算法里面的注释吧,注释很棒的
4.2、算法
public int maxProfit(int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
// f[i][0]: 手上持有股票的最大收益
// f[i][1]: 手上不持有股票,并且处于冷冻期中的累计最大收益
// f[i][2]: 手上不持有股票,并且不在冷冻期中的累计最大收益
int[][] dp = new int[n][3];
//第一天只能买入股票
dp[0][0] = -prices[0];
for (int i = 1; i < n; ++i) {
// Math.max (上一天第一次买入股票手里还剩多少钱 ,上一天不在冷冻区并且又在当天买入股票后手里还剩多少钱)
dp[i][0] = Math.max(dp[i - 1][0] , dp[i - 1][2] - prices[i] );
//准备进入冷冻区,上一天买入股票后,今天卖出股票后开始进入冷冻期
dp[i][1] = dp[i - 1][0] + prices[i];
// 不在冷冻期手里剩多少钱 Math.max (上一天不在冷冻期手里剩多少钱,上一天在冷冻期(那么今天就不是冷冻期)手里还剩多少钱)
dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1]);
}
//手上不持有股票的时候,手里剩多少钱
return Math.max(dp[n - 1][1], dp[n - 1][2]);
}
4.3、测试
@Test
public void test() {
int[] prices = {1, 2, 3, 0, 2};
System.out.println(maxProfit(prices));
}