股票买入卖出问题

Let's assume that there is a simple market for beans. Every day there is a published bean price in the market. Traders can buy or sell at the published price. There is a trader who time travelled to future and brought back the price information for a number of days in the future. If you have this information and you are allowed to buy and sell many times. How do you make the maximum profit? The price information will be given as an array of numbers. Each number is for a day’s trading price. The numbers are all integers to simplify the problem. You will need to return the index of the buy-in point and sell-out point for maximum profit.

Rules:

1) The input line length less than 1000, and the trading price length less than 100;

2) The trading price is positive integer;

3) The trading prices are delimited  by ' '(single space);

4) Please make sure every buying and selling period shortest. especially, please ouput '-' if all the trading prices are the same or no trading point;

Sample Input and Output:

Input 1

1 3 5 4 2 8 10

Output 1

1 3 5 7

To make the maximum profit, you should buy at $1 and sell at $5, and then buy at $5 and sell it at $10. so the output is "1 3 5 7".

Input 2

1 1 1 3 5 4 2 2 2 8 10

Ouput 2

3 5 9 11

网上看到一道算法题目，类似leetcode中的股票买卖问题
但给出示例的input output结果却看不懂

新问题：可以多次交易
当天只可买卖一次
如何确定“every buying and selling period shortest”？

求解！！！

1 3 5 4 2 8 10 -＞1 3 5 7。第一天买进，第三天卖出，第五天买进，第七天卖出

mymiracle 发表于 2013-9-25 08:06
1 3 5 4 2 8 10 -＞1 3 5 7。第一天买进，第三天卖出，第五天买进，第七天卖出

晕，原来是天数啊
多谢~

mymiracle 发表于 2013-9-25 08:06
1 3 5 4 2 8 10 -＞1 3 5 7。第一天买进，第三天卖出，第五天买进，第七天卖出

新问题：
可以多次交易
当天只可买卖一次
如何确定“every buying and selling period shortest”？

求解！！！

zyp911 发表于 2013-9-25 13:48
新问题：
可以多次交易
当天只可买卖一次

every buying and selling period shortest 我理解就是 某个序列 1 1 1 1 3 5 那么应该最后一个1 买入，5 卖出。
就这个题而言，就是每个严格递增子序列取出来，尾减去头，再加起来

KevinFromJail 发表于 2013-9-25 14:07
every buying and selling period shortest 我理解就是 某个序列 1 1 1 1 3 5 那么应该最后一个1 买入，5 ...

嗯 没错
应该这样理解

不过这样回头看
Best Time to Buy and Sell Stock II
显得过于简单了

如果当天只能买卖一次
如果两次三次四次都可达到最大利益
如何判断交易次数

有时间能否给出合理代码？

zyp911 发表于 2013-9-25 16:19
嗯 没错
应该这样理解

本身大部分leetcode级别的算法题，重点就不在于算法的难度，而在于熟练程度。能不能尽快地写出bug free的代码才是面试成功与否的关键。
回到这个问题上，这个问题的关键点在于不同买卖序列是不能有交叉覆盖的。有交叉就要另外考虑了。在没有交叉的情况下，当天买卖一次和多次并没有什么区别。
比如1 3 5 4 2 6
第一天卖，第三天卖，第五天买，第六天卖
就算允许多次交易，但只要不交叉，那也没有更好的解法，仍然是找严格递增子序列。
有交叉的题，思路就不一样了，我暂时能想到的也就穷举搜索。找到一对买入卖出的点对之后，去掉搜索剩下的。