Pythonでk売買した後に私たちが稼ぐことができる最大の利益を見つけるためのプログラム

会社の株価を時系列で表すnumsという数値のリストがあり、別の値kもあるとすると、最大k個の売買から得られる最大の利益を見つける必要があります（購入する必要があります）。販売する前に、購入する前に販売する）。

したがって、入力がprices =[7、3、5、2、3] k =2のような場合、出力は3になります。これは、3で購入し、次に5で販売し、再び2で購入して販売できるためです。 3時。

これを解決するには、次の手順に従います-

• 関数dp（）を定義します。これにはi、k、購入が必要です
• iが価格のサイズと同じであるか、kが0と同じである場合、
  • 0を返す
• 購入したものが真の場合、
  • （dp（i + 1、k-1、False）+価格[i]）とdp（i + 1、k、購入済み）の最大値を返します
• それ以外の場合、
  • （dp（i + 1、k、True）-prices [i]）とdp（i + 1、k、購入済み）の最大値を返します
• メインメソッドからdp（0、k、False）を呼び出し、結果を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, prices, k):
      def dp(i, k, bought):
         if i == len(prices) or k == 0:
            return 0
         if bought:
            return max(dp(i + 1, k - 1, False) + prices[i], dp(i + 1, k, bought))
         else:
            return max(dp(i + 1, k, True) - prices[i], dp(i + 1, k, bought))

      return dp(0, k, False)

ob = Solution()
prices = [7, 3, 5, 2, 3]
k = 2
print(ob.solve(prices, k))

入力

[7, 3, 5, 2, 3], 2

出力

3