[LeetCode]122. Best Time to Buy and Sell Stock II 最好的买卖股票时机 第二季

题目地址:

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

题目描述:

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).

题目大意:

告诉你你现在有一个数组,数组中第 i 个元素就是第 i 天的股价。

设计一个算法去寻找最大的利益。你可以尽可能的去处理(比如说买一份之后在股票翻倍的时候卖一份)。然而,你不能够同时买卖。(比如说你必须在卖股票之前买一遍)


 

一开始我毫无思路。不过看到tag标签中greedy的贪心法,结合一下以前翻过的书,就想出了一些简单的方法。股票的曲线肯定有波动,那么什么时候要卖?是当股价低于买入时的价格时计算,还是一有下降趋势就卖?其实真是很纠结。因为股票本来就是个不以人的意志为转移的东西(卧槽这句话是这篇文章里最骚的。),所以其实我并没有很明白题目意思。

但之后看到自己的样例输出出现问题的时候,我就明白了,本题的作者是个投机者,他一遇到价格下降,就赶紧卖掉。

噢那就简单多了。

遇到了很多问题,一开始以为它只做买入卖出的一次,后来引入变量 profile 去计算最终盈利总和,还有到数组末尾要再加一次。

总的来说看到Accepted 还是挺开心的。

答案地址:http://www.cnblogs.com/ganganloveu/p/3764255.html

核心思想:每一段单调递增区间的收益累加。

 

这个前辈的代码让我知道股票是可以,看到涨了马上卖出去的做法。然后立刻再买入。不过仔细一想,我的思路和他一样。