卖萌的弱渣

I am stupid, I am hungry.

Best Time to Buy and Sell Stock III

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 at most two transactions.

Note:

You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution

  • DP
  • F1[i]: 在prices[i]前进行一次交易获得的最大利益 f1[i] = max(f1[i-1], prices[i]-minV)
  • F2[i]: 在prices[i]之后进行一次交易获得的最大利润 f2[i] = max(f2[i+1], maxV-prices[i])
  • 结果就是f1[i] + f2[i]
(Best-Time-to-Buy-and-Sell-Stock3.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """

        # f1,f2
        length = len(prices)
        if length == 0:
            return 0

        f1 = [0]*length
        f2 = [0]*length

        minV = prices[0]

        for i in range(1,length):
            f1[i] = max(f1[i-1],prices[i]-minV)
            minV = min(minV, prices[i])

        maxV = prices[length-1]
        for i in range(length-2,-1,-1):
            f2[i] = max(f2[i+1],maxV-prices[i])
            maxV = max(maxV, prices[i])
        ret = 0
        for i in range(length):
            if f1[i]+f2[i] > ret:
                ret = f1[i]+f2[i]
        return ret