Best Time to Buy and Sell Stock series.

股票收益最大化，一系列有五六个题目。

这里仅回顾我前进中的心路, 停下来, 做个小结。
未来两个月后，下一步，我会重新训练解题思路。

正文开始了，

Q: 允许交易两次的股票收益最大化，这道题是不是枚举/模拟类题目？
Q: 这个题我自己没有想出答案。有没有什么指南训练一下，可以提高解题水平？

我用的是两端扫描的办法，从左和从右扫描得到，每端的依次的最大收益值，然后再扫描一次，两边相加求最大值，时间复杂度还是o(n)。
A：左边和右边加起来，找到全局最大化。

去年夏天，第一次面试前端，问了普通数字和罗马数字转换，我就没有想出解题思路。
普通数字和罗马数字转换，应该是标准的模拟/枚举题目。

2. Best Time to Buy and Sell Stock with Transaction Fee

这道题我毫无头绪。卡住两三天。
这一类题目，该怎么学习和训练呢？

大师点拨：
A：
This is a DP and Greedy related problem, I don't think you learn the algorithm yet.
It will be taught in advanced algorithm jiuzhang class. I will suggest you to skip.

At this moment, you are not the scientist who can invent the algorithm.
In fact almost all people are NOT. This is why...

😇 谢谢分析和打气鼓励。

据说最好的学习策略，就是不断的取得小胜利，我在这个问题上两三天取得了一个大失败，觉得很受挫折。
猛一看像是个简单的小问题，就想给他一举拿下。
这是九章算法班，最后一节课前缀和知识点，引出了一个股票交易问题，没想到延伸出了五六个问题，整个做法思路都变样了。
特别是这一道题，facebook考过，我就想着应该做出来。也算一个准备。

我的直观解法，通过了一多半测试，总是不甘心。
谢谢大师点拨，让我从死胡同里解脱出来，摆正心态，继续前进。

附录:

The hardest problem in this series.

393. Best Time to Buy and Sell Stock IV
lc, https://www.lintcode.com/problem/best-time-to-buy-and-sell-stock-iv

constraint: trade k times, get max gain.

idea:

我自己都没有搞清楚是怎么通过测试验收的. 虽然代码是我从头写出来的。

essential code:

    def maxProfit(self, k, prices):
        if not prices or len(prices) == 1:
            return 0
        buy = -prices[0]
        sell = 0
        if k > len(prices):
            for price in prices:
                buy = max(buy, sell - price)  # core code 
                sell = max(sell, buy + price)  # core code 
            return sell
        buys = [-float("inf")] * k
        sells = [0] * k
        for price in prices:
            buys[0] = max(buys[0], -price)
            for i in range(k):
                if i > 0:
                    buys[i] = max(buys[i], sells[i - 1] - price)
                sells[i] = max(sells[i], buys[i] + price)
        return sells[k - 1]