title: best time to buy and sell stock dynamic programming
body: <p>Trying to solve <a href="https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/" rel="nofollow noreferrer">this</a>: Say you have an array for which the ith element is the price of a given stock on day i.</p>
  
  <p>Design an algorithm to find the maximum profit. You may complete at most two transactions.</p>
  
  <p>Solution:
  What i am doing is divide and conquer kind of approach.</p>
  
  <p><em>dp[i][j]</em> is the maximum profit between <em>ith</em> and <em>jth</em> day.Calculated as below:</p>
  
  <p><em>dp[i][j] = max(dp[i][j], max(prices[i] - prices[j], dp[k][j], dp[i][k+1]))</em>, where k is less than i and greater than j.</p>
  
  <p>Now all we need is below to find out the maximum profit in two transactions:</p>
  
  <p><em>m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))</em></p>
  
  <p>Please give me <strong>just hint</strong> to solve this problem as the existing solution presented here is timing out.</p>
  
  <pre><code>class Solution(object):
      def profit(self, prices, dp):
          m = 0
          for w in range(1, len(prices)):
              for i in range(1, len(prices)):
                  for j in range(i-w, i):
                      if i-w &lt; 0:
                          continue
                      for k in range(j, i):
                          dp[i][j] = max(dp[i][j], max(prices[i] - prices[j], dp[k][j], dp[i][k+1]))
                          m = max(m, max(dp[i][j], dp[k][j] + dp[i][k+1]))
          return m
  
      def maxProfit(self, prices):
          """
          :type prices: List[int]
          :rtype: int
          """
          dp = [[0 for i in range(len(prices)+1)] for i in range(len(prices)+1)]
          return self.profit(prices, dp)
  </code></pre>