"""
Your are given an array of integers prices, 
for which the i-th element is the price of a given stock on day i; 
and a non-negative integer fee representing a transaction fee.

You may complete as many transactions as you like, 
but you need to pay the transaction fee for each transaction. 
You may not buy more than 1 share of a stock at a time 
(ie. you must sell the stock share before you buy again.)

Return the maximum profit you can make.

Example 1:
Input: prices = [1, 3, 2, 8, 4, 9], fee = 2
Output: 8
Explanation: The maximum profit can be achieved by:
    Buying at prices[0]  = 1
    Selling at prices[3] = 8
    Buying at prices[4]  = 4
    Selling at prices[5] = 9
    The total profit is ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
"""
class Solution(object):
    def maxProfit2(self, prices, fee):
        """
        Dynamic Programming. Time Limit exceeded solution.
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        dp = [[0] * len(prices) for i in range(2)]
        for i in range(1, len(prices)):
            for j in range(0, i):

                if prices[i] - fee > prices[j]:
                    #print(str(prices[i]) + " j is: " + str(j))
                    prev = max(dp[0][j], dp[1][j])
                    dp[0][i] = max(prices[i] - fee - prices[j] + prev, dp[0][i])
            dp[1][i] = max(dp[1][i - 1], dp[0][i - 1])
        for row in dp:
            print(row)
        return max(dp[0][len(prices) - 1], dp[1][len(prices) - 1])