BestTimeToBuyAndSellStockII [source code]

public class BestTimeToBuyAndSellStockII {
    public int maxProfit(int[] prices) {
        int res = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i-1]) res += prices[i] - prices[i - 1];
        }
        return res;
    }
}

这个题目刚开始看题目有点没看懂, 感觉题目里面很多信息都没有讲清楚, 比如你拥有多少 share. 不过从别人的答案来看, 其实你一开始是没有任何的 stock 的, 然后你每次只能持有一个 share. 然后你的任务就是低进高出, 投机买卖就行了;

如果 lc 里面实在碰到这种看不懂题目的, 可以先空代码, 跑一下看看, 然后自己 custom 编一个 case, 看看他的答案给的是什么.

不过如果实际的面试碰到这个不知道怎么办; 估计面试官应该是会给几个样例 case 的;

这个是作者的思考过程, 可以看到他也是从小的例子开始的:

You thought too much. If you talk about multiple day, say 3 days, and the price is 3,1,5, and you thought about 3 buy, 5 sell. But actually you will make the most if buy at 1 and sell at 5. If the price is 3,9,5, the best would just do 3->9, and forget about the 5. If 3,4,5, you can say 3->5 is the best, but my code will give you 3->4 and 4->5, which is the same.

我自己当时思考的时候上来就是一个长度为6的例子, 结果并不容易看出来规律.

感觉我这个毛病也是不好改了;

这个是另外一个人对这个问题的看法:

No question is a joke. This question is indeed the interview question I encountered interviewing with Goldman Sachs. Interview questions from financial organization my be a lot simpler to solve. But it requires higher level of clarity when it comes to explaining your thought. And most importantly, arrogance is the first thing you want to avoid during interview. Don't murder me if you don't like my comment. LOL

虽然这个题目有点奇怪, 不过可以学习的东西还是很多的;

/However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again)./
I think that note may mean "you can't sell and buy at the same time position".
Take "1 2 3" for example, you should 0+(3-1) instead of 0+(2-1)+(3-2)
It may leave out a lot of add operation.

这个是另外一个人的观点, 这个确实阐述了这个算法背后隐藏的一些复杂性;

总体来说这个问题考察的其实并不是算法知识, 更多的就是类似商业上的一个常识, 或者一点math insight;
理论上可以这样分析这个问题: 如果明天的价格比今天高, 那我今天应该buy, 因为至少可以盈利. 如果后天比明天高, 那么明天应该 hold. 如果后天比明天低, 明天应该 sell. 然后后天再决定是否可以 buy(如果后天以后没有任何比后天高的价格, 跌停牌, 那么后天就不 buy). 这个其实可以算是一个类似的 greedy 的思路: 站在今天, 只要明天可以盈利, 我今天就买进;

Problem Description

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Difficulty:Easy
Category:Algorithms
Acceptance:46.59%
Contributor: LeetCode
Companies
bloomberg
Related Topics
array greedy
Similar Questions
Best Time to Buy and Sell Stock Best Time to Buy and Sell Stock III Best Time to Buy and Sell Stock IV Best Time to Buy and Sell Stock with Cooldown