Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで最大の合計を持つ連続したサブリストの合計を見つけるプログラム

配列Aがあるとします。最大合計を持つ連続したサブリストを見つけ、その合計を返す必要があります。したがって、配列AがA =[-2,1、-3,4、-1,2,1、-5,4]のようである場合、合計は6になります。サブ配列は[4、-1になります。 2、1]。

これを解決するために、動的計画法のアプローチを使用してみます。

  • Aのサイズと同じ配列dpを定義し、0で埋めます

  • dp [0]：=A [0]

  • for i：=1からAのサイズ– 1

    • dp [i]：=最大dp [i – 1] +A[i]およびA[i]

  • dpで最大値を返す

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

例

class Solution(object):
   def solve(self, nums):
      dp = [0 for i in range(len(nums))]
      dp[0] = nums[0]
      for i in range(1,len(nums)):
         dp[i] = max(dp[i-1]+nums[i],nums[i])
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.solve(nums))

入力

[-2,1,-3,7,-2,2,1,-5,4]

出力

8

  1. Pythonを使用して最大の確率でパスを見つけるプログラム

    n個のノード（ノードには0から番号が付けられます）を持つ無向加重グラフがあるとします。このグラフは、エッジリストを使用して入力として与えられ、各エッジeについて、そのエッジ確率[e]を通過する成功の確率があります。開始ノードと終了ノードもあります。最初から最後まで成功の確率が最大のパスを見つけて、成功の確率を返す必要があります。パスが見つからない場合は、0を返します。 したがって、入力が次のような場合 ノード0から2へのパスが2つあるため、出力は0.24になります。1つは確率0.2、もう1つはノード1を経由するパスの確率は0.4 * 0.6 =0.24で、これが最大です。 これを解

  2. Pythonでツリーの隣接していないノードの最大合計を見つけるプログラム

    二分木があるとすると、2つの値が親から子に隣接できない場合に、取得できる値の最大合計を見つける必要があります。 したがって、入力が次のような場合 10、4、3が互いに隣接していないため、出力は17になります。 これを解決するには、次の手順に従います- 関数f（）を定義します。これはノードを取ります ノードがnullの場合、 return（0、0） （a、b）：=f（ノードの左側） （c、d）：=f（ノードの右側） ペアを返します（ノード+ b+dとa+c、a + cの値の最大値） メインメソッドからf（root）を呼び出し、その最初の値を返します 理解を深めるために、次