<jupyter_start><jupyter_text>Best Time to Buy and Sell Stock TwiceYou are given an array prices where prices[i] is the price of a given stock on the ith day.Find the maximum profit you can achieve. You may complete at most two transactions.Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).Example 1:```Input: prices = [3,3,5,0,0,3,1,4]Output: 6Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.```Example 2:```Input: prices = [1,2,3,4,5]Output: 4Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.```Example 3:```Input: prices = [7,6,4,3,1]Output: 0Explanation: In this case, no transaction is done, i.e. max profit = 0.```Example 4:```Input: prices = [1]Output: 0```**Constraints**:  * 1 5* 0 5  Approach 1: Devide and conqueTransform this problem to two sub problems of buying and selling once. Let f(k) is the max profit when the first sell is at index k, then: f(k) = p(0,k) + p(k+1, len(prices)) when p(i,j)m denotes buying at index i and selling at j.Next is to let k iterate the array and count the global max.* Time complexity: $O(n^2)$* Space complexity: $O(n)$<jupyter_code>from typing import List

def buy_and_sell_stock_once(prices: List[float]) -> float:
    if not prices or len(prices) == 1: return 0
    max_profit = 0
    min_price = prices[0]
    for p in prices:
        max_profit = max(max_profit, p - min_price)
        if p < min_price:
            min_price = p
    return max_profit

def buy_and_sell_stock_twice(prices: List[float]) -> float:
    max_profit = 0
    for k in range(len(prices)):
        profit1 = buy_and_sell_stock_once(prices[:k])
        profit2 = buy_and_sell_stock_once(prices[k:])
        max_profit = max(max_profit, profit1+profit2)
    return max_profit

assert buy_and_sell_stock_twice([3,3,5,0,0,3,1,4]) == 6
assert buy_and_sell_stock_twice([1,2,3,4,5]) == 4
assert buy_and_sell_stock_twice([7,6,4,3,1]) == 0<jupyter_output><empty_output><jupyter_text>Note: The algorithm did not pass the Leetcode online test at test case 202/214 due to time limit exceeded.  It takes a long time to run on a 50000 long increasing array.  Approach 2: Dynamic programmingIn dynamic programming algorithms, normally we create an array of one or two dimensions to keep the intermediate optimal results. In this problem though, we would use two arrays, with one array keeping the results of sequence from left to right and the other array keeping the results of sequence from right to left.Now, if we divide the sequence of prices around the element at the index i, into two subsequences, with left subsequences as Prices[0], Prices[1], ... Prices[i] and the right subsequence as Prices[i+1], ... Prices[N-1], then the total maximum profits that we obtain from this division (denoted as max_profits[i]) can be expressed as follows: `max_profits[i] = left_profits[i] + right_profits[i+1]`For example, if prices = [7, 1, 5, 3, 6, 4]:```left_profits: 0 0 4 4 5 5               \ \ \ \ \   right_profits:5 5 3 3 0 0```Thus, the max profits will be max of [5, 3, 7, 4, 5], which is 7.Inspired by the Leetcode solutoin: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/solution/<jupyter_code>def buy_and_sell_stock_twice_dp(prices):
    """
    :type prices: List[int]
    :rtype: int
    """
    if len(prices) <= 1:
        return 0

    left_min = prices[0]
    right_max = prices[-1]

    length = len(prices)
    left_profits = [0] * length
    # pad the right DP array with an additional zero for convenience.
    right_profits = [0] * (length + 1)

    # construct the bidirectional DP array
    for l in range(1, length):
        left_profits[l] = max(left_profits[l-1], prices[l] - left_min)
        left_min = min(left_min, prices[l])

        r = length - 1 - l
        right_profits[r] = max(right_profits[r+1], right_max - prices[r])
        right_max = max(right_max, prices[r])

    max_profit = 0
    for i in range(0, length):
        max_profit = max(max_profit, left_profits[i] + right_profits[i+1])

    return max_profit
assert buy_and_sell_stock_twice_dp( [7, 1, 5, 3, 6, 4]) == 7
assert buy_and_sell_stock_twice_dp([3,3,5,0,0,3,1,4]) == 6
assert buy_and_sell_stock_twice_dp([1,2,3,4,5]) == 4
assert buy_and_sell_stock_twice_dp([7,6,4,3,1]) == 0<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.11207269580268282, 'fraction_numerical': 0.037213327563825185, 'mean_word_length': 3.92332268370607, 'pattern_counts': {'":': 0, '<': 11, '<?xml version=': 0, '>': 11, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '2', 'dir': 'jupyter-structured-clean-dedup', 'id': '549842', 'license': 'Apache-2.0', 'n_tokens_mistral': 1683, 'n_tokens_neox': 1554, 'n_words': 570, 'path': 'array/Best Time to Buy and Sell Stock Twice.ipynb', 'repo_name': 'iShiBin/algorithm', 'size': '4622'}