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

package main

import (
	"fmt"
)

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

func main() {
	var n int
	_, err := fmt.Scan(&n)
	for err == nil {
		prices := make([]int, n)
		for i := 0; i < n; i++ {
			fmt.Scan(&prices[i])
		}

		// ldp 表示昨天的状态
		// dp 表示今天的状态
		// dp[i][j] 表示剩余i次购买机会，且持有j份股票时，当天所能活动的的最大收益
		// 空间复杂度为O(1)
		// ----------------------------------------------------------------
		// 初始化第0天状态，ldp[i][0]表示不购入股票，收益为0
		// （或重复购入然后马上卖出，由于这种无意义操作完全不影响收益，将所有无意义操作移
		// 动至第0天处理，后续不再考虑无意义操作）
		// ldp[0][1]、ldp[1][1]表示第0天最后购入股票未卖出，收益为负
		// ldp[2][1]表示第0天剩余2次购买机会（未消耗购买机会），但却持有股票，为不可能
		// 事件，收益设置为负无穷大
		ldp := [3][2]int{{0, -prices[0]}, {0, -prices[0]}, {0, -(1 << 31)}}
		var dp [3][2]int
		// 时间复杂度度为O(n)
		for i := 1; i < n; i++ {
			// 今天剩余0/1次购买机会，且持有股票，有2种可能：昨天就持有股票今天无操作，
			// 或昨天未持有股票今天消耗一次购买机会买入
			dp[0][1] = max(ldp[0][1], ldp[1][0]-prices[i])
			dp[1][1] = max(ldp[1][1], ldp[2][0]-prices[i])
			// 今天剩余2次购买机会，但却持有股票，为不可能事件，收益设置为负无穷大
			dp[2][1] = -(1 << 31)

			// 今天剩余i次购买机会，且未持有股票，有2种可能：昨天持有股票今天卖出，或昨
			// 天就未持有股票今天无操作
			dp[0][0] = max(ldp[0][0], ldp[0][1]+prices[i])
			dp[1][0] = max(ldp[1][0], ldp[1][1]+prices[i])
			dp[2][0] = max(ldp[2][0], ldp[2][1]+prices[i])

			// “今天”变为“昨天”
			ldp = dp
		}
		fmt.Println(dp[0][0])

		_, err = fmt.Scan(&n)
	}
}