122.M 买卖股票的最佳时机 II

Problem: 122. 买卖股票的最佳时机 II

思路

思路1：贪心算法 由于不限制买卖次数，最大利润就是能够抓住每一天的涨幅，所以算法是如果把所有的连续两天的正收益都累加起来。

思路2：动态规划

定义状态转移dp[i][0]为第i天不持有股票的最大利润，dp[i][1]表示第i天持有股票的最大利润。

状态转移方程为：

dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])

Code

func maxProfit(prices []int) int {
	profit := 0
	for i := 1; i < len(prices); i++ {
		if prices[i]-prices[i-1] > 0 {
			profit += prices[i] - prices[i-1]
		}
	}

	return profit
}

代码2：

func maxProfit(prices []int) int {
	if len(prices) <= 1 {
		return 0
	}

	length := len(prices)
	dp := make([][2]int, length)
	dp[0][0] = 0
	dp[0][1] = -prices[0]

	for i := 1; i < len(prices); i++ {
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
	}

	return dp[length-1][0]
}

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

	return b
}