买卖股票的最佳时机

买卖股票的最佳时机，各种相关问题

func maxProfit2(k int, prices []int) int {
	if len(prices) == 0 || k == 0 {
		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {
		dp[i] = make([]int, 2*k+1)
	}
	for i := 0; i < 2*k+1; i++ {
		if i%2 == 0 {
			dp[0][i] = 0
		} else {
			dp[0][i] = -prices[0]
		}
	}
}

//买卖股票的最佳时机 可以买卖多次
// 问题描述
// 给定一个数组 prices ，其中 prices[i] 表示股票第 i 天的价格。

// 在每一天，你可能会决定购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以购买它，然后在 同一天 出售。
// 返回 你能获得的 最大 利润 。

func maxProfit(prices []int) int {
	if len(prices) == 1 {
		return 0
	}
	length := len(prices)
	dp := make([][]int, length)
	for i := 0; i < length; i++ {

		dp[i] = make([]int, 2)
	}
	dp[0][0] = -prices[0]
	for i := 0; i < length; i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])
		dp[i][1] = max(dp[i-1][0]+prices[i], dp[i-1][1])
	}
	return dp[length-1][1]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 买卖股票的最佳时机 限定交易次数
// 问题描述
// 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）

func maxProfit33(prices []int) int {
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {

		dp[i] = make([]int, 5)
	}
	dp[0][0] = 0
	dp[0][1] = -prices[0]
	dp[0][2] = 0
	dp[0][3] = -prices[0]
	dp[0][4] = 0
	for i := 1; i < len(prices); i++ {
		dp[i][0] = dp[i-1][0]                            //没做交易，原来啥样还啥样
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) //不要顺应上面的思路思考 上一次和本次比
		dp[i][2] = max(dp[i-1][2], dp[i-1][1]+prices[i])
		dp[i][3] = max(dp[i-1][3], dp[i-1][2]-prices[i])
		dp[i][4] = max(dp[i-1][4], dp[i-1][3]+prices[i])
	}
	return dp[len(prices)-1][4]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//买卖股票的最佳时机 限定交易次数k
// 问题描述
// 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。

// 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。

// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

func maxProfit3333(k int, prices []int) int {
	if len(prices) == 0 || k == 0 {

		return 0
	}
	dp := make([][]int, len(prices))
	for i := 0; i < len(prices); i++ {

		dp[i] = make([]int, 2*k+1)
	}
	for i := 0; i < 2*k+1; i++ {

		if i%2 == 0 {
			dp[i][0] = 0
		} else {
			dp[i][0] = -prices[0] //反正是要买入，但是买入那天股票价格是变动的
		}
	}

	for i := 1; i < len(prices); i++ {
		dp[i][0] = dp[i-1][0] //价格变动 但是第0次就是不交易 所以手里股票总价值不变
		for j := 1; j < 2*k+1; j++ {
			if j%2 == 0 {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+prices[i]) //
			} else {
				dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i])
			}
		}
	}
	return dp[len(prices)-1][2*k]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

// 买卖股票的最佳时机 含冷冻期
// 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。

// 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

// 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
// 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

func maxProfit4444(prices []int) int {
	length := len(prices)
	res := make([][]int, length)
	for i := 0; i < len(res); i++ {
		res[i] = make([]int, 4)
	}
	res[0][0] = -prices[0]
	for i := 1; i < len(res); i++ {

		res[i][0] = max(res[i-1][0], max(res[i-1][1]-prices[i], res[i-1][3]-prices[i]))
		res[i][1] = max(res[i-1][1], res[i-1][3])
		res[i][2] = res[i-1][0] + prices[i]
		res[i][3] = res[i-1][2]
	}
	return max(res[length-1][1], max(res[length-1][2], res[length-1][3]))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

//买卖股票的最佳时机 含手续费
// 题目:给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

// 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

// 返回获得利润的最大值。

// 注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

 

// 示例 1：

// 输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
// 输出：8
// 解释：能够达到的最大利润:  
// 在此处买入 prices[0] = 1
// 在此处卖出 prices[3] = 8
// 在此处买入 prices[4] = 4
// 在此处卖出 prices[5] = 9
// 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
// 示例 2：

// 输入：prices = [1,3,7,5,10,3], fee = 3
// 输出：6
 

// 提示：

// 1 <= prices.length <= 5 * 104
// 1 <= prices[i] < 5 * 104
// 0 <= fee < 5 * 104

func maxProfit6(prices []int, fee int) int{
	n : =len(prices)
	if n <= 0{
		return 0
	}
	hold := make([]int,n)
	unhold := make([]int,n)
	hold[0] = -prices[0]
	unhold[0] = 0 
	for i :=1;i<n;i++{
		hold[i] = max(hold[i-1],unhold[i-1]-prices[i])
		unhold[i] = max(unhold[i],hold[i-1]+prices[i]-fee)
	}
	return unhold[n-1]
}

func max(a,b int) int{
	if a > b{
		return a 
	}
	return b 
}