122.买卖股票的最佳时机 II
动态规划
考虑两个状态,天数和当天是否持有股票,不同状态下当天持有的最大现金:
当天持有股票:前一天持有并且当天不卖或者前一天没有当天买入。
当天没有持有股票:前一天没有持有并且当天不买或者前一天持有当天卖出。
最后一天不持有股票状态下的现金为最大值。
由于第n天的现金只与前一天的现金和是否持有股票有关,所以优化空间只用记录前一天持有和不持有股票的现金即可。
时间复杂度: O(N)
空间复杂度:O(1)
1 |
|
122.买卖股票的最佳时机 II
https://blog.jerrylee.me/2021/09/8a1aa3ad11a7.html