Module Expr Str Assign NameStore Str ClassDef bases body FunctionDef arguments args NameParam NameParam defaults body Expr Str If CompareLtE Call NameLoad NameLoad Num body Return Num Assign NameStore ListComp Num comprehension NameStore Call NameLoad Call NameLoad NameLoad Assign NameStore SubscriptLoad NameLoad Index Num For NameStore Call NameLoad Num Call NameLoad NameLoad body Assign SubscriptStore NameLoad Index NameLoad Call NameLoad SubscriptLoad NameLoad Index BinOpSub NameLoad Num BinOpSub SubscriptLoad NameLoad Index NameLoad NameLoad Assign NameStore Call NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad Assign NameStore ListComp Num comprehension NameStore Call NameLoad Call NameLoad NameLoad Assign NameStore SubscriptLoad NameLoad Index Num For NameStore Call NameLoad BinOpSub Call NameLoad NameLoad Num Num Num body Assign SubscriptStore NameLoad Index NameLoad Call NameLoad SubscriptLoad NameLoad Index BinOpAdd NameLoad Num BinOpSub NameLoad SubscriptLoad NameLoad Index NameLoad Assign NameStore Call NameLoad SubscriptLoad NameLoad Index NameLoad NameLoad Assign NameStore Num For NameStore Call NameLoad Call NameLoad NameLoad body Assign NameStore Call NameLoad NameLoad BinOpAdd SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index NameLoad Return NameLoad decorator_list FunctionDef arguments args NameParam NameParam defaults body Expr Str If CompareLtE Call NameLoad NameLoad Num body Return Num Assign NameStore ListLoad For NameStore Call NameLoad Num Call NameLoad NameLoad body Expr Call AttributeLoad NameLoad attr BinOpSub SubscriptLoad NameLoad Index NameLoad SubscriptLoad NameLoad Index BinOpSub NameLoad Num Assign NameStore ListLoad Num Num Assign NameStore Num Assign NameStore Num For NameStore Call NameLoad Call NameLoad NameLoad body If CompareGtE BinOpAdd NameLoad SubscriptLoad NameLoad Index NameLoad Num body AugAssignAdd NameStore SubscriptLoad NameLoad Index NameLoad Assign NameStore Call NameLoad NameLoad NameLoad orelse If CompareGt NameLoad SubscriptLoad NameLoad Index Num body Assign SubscriptStore NameLoad Index Num SubscriptLoad NameLoad Index Num Assign SubscriptStore NameLoad Index Num NameLoad orelse If CompareGt NameLoad SubscriptLoad NameLoad Index Num body Assign SubscriptStore NameLoad Index Num NameLoad Assign NameStore Num Assign NameStore Num Return Call NameLoad NameLoad decorator_list decorator_list
N/A N/A 
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).
 N/A __author__ Danyang Solution N/A N/A maxProfit N/A N/A self prices N/A N/A N/A 
        Algorithm: dp
        1-D dp.
        Given an i, split the whole array into TWO parts:
        [0... i] and [i+1... n-1], it generates two max value based on i, max_profit[0... i] and max_profit[i+1... n-1]

        global_max_profit = max(max_profit[0... i] + max_profit[i+1... n-1]), for all i.

        :param prices: list of integers
        :return: integer
         N/A N/A N/A len prices 1 N/A N/A 0 N/A forward N/A 0 N/A _ N/A xrange N/A len prices N/A lowest_buy_price N/A prices N/A 0 N/A i N/A xrange 1 N/A len prices N/A N/A N/A forward N/A i N/A max N/A forward N/A N/A i 1 N/A N/A prices N/A i lowest_buy_price N/A lowest_buy_price N/A min N/A prices N/A i lowest_buy_price N/A backward N/A 0 N/A _ N/A xrange N/A len prices N/A highest_sell_price N/A prices N/A -1 N/A i N/A xrange N/A N/A len prices 2 -1 -1 N/A N/A N/A backward N/A i N/A max N/A backward N/A N/A i 1 N/A highest_sell_price N/A prices N/A i N/A highest_sell_price N/A max N/A prices N/A i highest_sell_price N/A max_profit 0 N/A i N/A xrange N/A len prices N/A N/A max_profit N/A max max_profit N/A N/A forward N/A i N/A backward N/A i N/A max_profit N/A maxProfit_error N/A N/A self prices N/A N/A N/A 
        2 transactions
        you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

        :param prices: list of integers
        :return: integer
         N/A N/A N/A len prices 1 N/A N/A 0 N/A delta_prices N/A N/A i N/A xrange 1 N/A len prices N/A N/A N/A N/A delta_prices append N/A N/A prices N/A i N/A prices N/A N/A i 1 N/A max_profits N/A 0 0 N/A max_sub_array 0 N/A current_sub_array 0 N/A j N/A xrange N/A len delta_prices N/A N/A N/A N/A current_sub_array N/A delta_prices N/A j 0 N/A N/A current_sub_array N/A delta_prices N/A j N/A max_sub_array N/A max max_sub_array current_sub_array N/A N/A N/A max_sub_array N/A max_profits N/A 0 N/A N/A N/A max_profits N/A 1 N/A max_profits N/A 0 N/A N/A max_profits N/A 0 max_sub_array N/A N/A N/A max_sub_array N/A max_profits N/A 1 N/A N/A N/A max_profits N/A 1 max_sub_array N/A max_sub_array 0 N/A current_sub_array 0 N/A N/A sum max_profits N/A N/A