题解 | #买卖股票的最好时机(一)#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param prices int整型一维数组
 * @return int整型
 */
func maxProfit(prices []int) int {
	// write code here
	n := len(prices)
	// dp[i][0] 表示某天不持股到该天为止的最大收益
	// dp[i][1] 表示某天持股到该天为止的最大收益
	dp := make([][2]int, n)
	// 第一天不持股，总收益为 0
	dp[0][0] = 0
	// 第一天持股，总收益为减去该天的股价
	dp[0][1] = -prices[0]
	for i := 1; i < n; i++ {
		// 当天不持股
		// 前面的若干天中卖掉了或是还没买，因此到此为止的总收益和前一天相同
		// 也有可能是当天才卖掉
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
		// 当天持股
		// 有可能是前面若干天中买了股票，当天还没卖因此收益与前一天相同
		// 也有可能是当天买入，此时收益为负的股价
		dp[i][1] = max(dp[i-1][1], -prices[i])
	}

	//最后一天不持股，到该天为止的最大收益
	return dp[n-1][0]
}

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

	return b
}