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

Example

Given an example [2,1,2,0,1], return 2

Solution

对比记忆, 贪心法的关键是判断长势,也就是把每次可以获得的利润叠加起来,可以得到一个不计次数的最大获利结果。而subarray 判断的是一个范围则是running number.

题意: 你可以做多笔操作,买入,卖出,求最大的利润。

初始low 的值是数组的第一个元素,可以使用 x < sys.maxsize, 保证第一次可以进入循环。

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    #贪心算法,得出不计次数的买卖的最大利润。
    def maxProfit(self, prices):
        total = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i-1]:
                total += prices[i] - prices[i-1]
        return total

Last updated

Was this helpful?