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).
思路很简单,只要看到价格涨,就在最低点买进,最高点卖出!
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ # buy at lowest value, and sell it at highest if not prices: return 0 ans = 0 lowest = highest = prices[0] is_grow = False for i in xrange(1, len(prices)): if prices[i] > prices[i-1]: highest = prices[i] is_grow = True else: if is_grow: # ^ point ans += highest - lowest lowest = prices[i] is_grow = False if is_grow: ans += highest - lowest return ans
直接绘图就知道上面解法和下面是等价的:
就是贪心,看到涨就买进卖出!!!
public class Solution { public int maxProfit(int[] prices) { int total = 0; for (int i=0; i< prices.length-1; i++) { if (prices[i+1]>prices[i]) total += prices[i+1]-prices[i]; } return total; }
还有贪心的解法,先找到最低点,再找最高点:
class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ # buy at lowest value, and sell it at highest if not prices: return 0 ans = 0 i = 0 length = len(prices) # 3 2 1 # 1 2 3 while i < length: while i<length-1 and prices[i]>=prices[i+1]: i += 1 if i == length-1: break lowest = prices[i] while i<length-1 and prices[i]<prices[i+1]: i += 1 ans += prices[i]-lowest #到这里,只能是i==length-1(也是因为一直涨到数组over) 或者是遇到了^转折点 i += 1 return ans