admin 管理员组

文章数量: 887021

Suppose that you have been offered the opportunity to invest in the Volatile Chemical Corporation. Like the chemicals the company produces, the stock price of the Volatile Chemical Corporation is rather volatile. You are allowed to buy one unit of stock only one time and then sell it at a later date, buying and selling after the close of trading for the day. To compensate for this restriction, you are allowed to learn what the price of the stock will be in the future. Your goal is to maximize your profit.


The problem 1: you are allowed to complete transaction only once, how do you calculate the max profit you may get?

def max_profit_1(prices):
    max_profit = 0
    n = len(prices)
    if n > 1:
        min_price = prices[0]
        i = 1
        while i < n:
            if prices[i] > min_price:
                profit = prices[i] - min_price
                if profit > max_profit:
                    max_profit = profit
            else:
                if min_price > prices[i]:
                    min_price = prices[i]
            i += 1
    return max_profit

The problem 2: you are allowed to complete at most two transactions, how do you calculate the max profit you may get?

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

def max_profit_2(prices):
    max_profit = 0
    n = len(prices)
    if n > 1:
        left = [0 for i in range(n)]
        right = [0 for i in range(n)]
        min_price = prices[0]
        i = 1
        while i < n:
            if prices[i] > min_price:
                profit = prices[i] - min_price
                if profit > max_profit:
                    max_profit = profit
            else:
                min_price = prices[i]
            left[i] = max_profit
            i += 1
        max_profit = 0
        i = n - 2
        max_price = prices[n - 1]
        while i >= 0:
            if prices[i] < max_price:
                profit = max_price - prices[i]
                if max_profit < profit:
                    max_profit = profit
            else:
                max_price = prices[i]
            right[i] = max_profit
            i -= 1
        i = 1
        max_profit = left[n - 1]
        while i < n - 2:
            profit = left[i] + right[i + 1]
            if profit > max_profit:
                max_profit = profit
            i += 1
    return max_profit

The problem 3: you are allowed to complete transactions at most k (>2) times, how do you calculate the max profit you may get?

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

def max_profit_matrix(prices):
    n = len(prices)
    assert n > 1
    ret = [[0 for i in range(n)] for j in range(n - 1)]
    for i in range(n - 1):
        min_price = prices[i]
        max_profit = 0
        j = i + 1
        while j < n:
            if prices[j] > min_price:
                profit = prices[j] - min_price
                if profit > max_profit:
                    max_profit = profit
            else:
                min_price = prices[j]
            ret[i][j] = max_profit
            j += 1
    return ret

def max_profit_k(prices, k):
    assert k > 2
    max_profit = 0
    n = len(prices)
    if n > 1:
        M = max_profit_matrix(prices)
        cache = [[0 for i in range(n + 1)] for j in range(2)]
        max_price = prices[n - 1]
        max_profit = 0
        i = n - 2
        while i >= 0:
            if prices[i] < max_price:
                profit = max_price - prices[i]
                if profit > max_profit:
                    max_profit = profit
            else:
                max_price = prices[i]
            cache[0][i] = max_profit
            i -= 1
        prev = 0
        curr = 1
        r = 2
        while r <= k:
            for i in range(n - 1):
                j = i + 1
                max_profit = cache[prev][i]
                while j < n:
                    profit = M[i][j] + cache[prev][j + 1]
                    if profit > max_profit:
                        max_profit = profit
                    j += 1
                cache[curr][i] = max_profit 
            prev = curr
            curr = ((curr + 1) & 1)
            r += 1
        max_profit = cache[prev][0]
    return max_profit

The test code: 

if __name__ == "__main__":
    prices = [100, 113, 110, 85, 105, 102, 86, 63, 81, 101, 94, 106, 101, 79, 94, 90, 97]
    assert max_profit_1(prices) == 43
    assert max_profit_2(prices) == 63
    assert max_profit_k(prices, 3) == 81
    assert max_profit_k(prices, 4) == 94

本文标签： Maximum Subarray Problem

版权声明：本文标题：The Maximum-Subarray Problem 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1725943208h896563.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。