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

Pythonの最大サブアレイ

整数配列Aがあるとします。長さが少なくとも1で、合計が最大である連続したサブ配列を見つけて、その合計を返す必要があります。したがって、配列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 to the size of A – 1
    • dp [i]：=最大dp [i – 1] +A[i]およびA[i]
  • 最大値をdpで返す

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

例（Python）

class Solution(object):
   def maxSubArray(self, nums):
      """
      :type nums: List[int]
      :rtype: int
      """
      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])
      #print(dp)
      return max(dp)
nums = [-2,1,-3,7,-2,2,1,-5,4]
ob1 = Solution()
print(ob1.maxSubArray(nums))

入力

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

出力

8

  1. Pythonでの最短のソートされていない連続サブアレイ

    整数配列があるとすると、1つの連続したサブ配列を見つける必要があります。そのサブ配列を昇順で並べ替えるだけで、配列全体も並べ替えられます。そのような最短のサブアレイを見つけて、その長さを出力する必要があります。したがって、配列が[2,6,4,8,10,9,15]の場合、出力は5になります。配列は[6,4,8,10,9]になります。 これを解決するには、次の手順に従います- res：=numsを配列として並べ替える ans：=0 rをリンクリストとして設定 0からresの長さまでの範囲のiの場合 nums[i]がres[i]と同じでない場合は、iをrに挿入します

  2. Pythonプログラムは最大3つ。

    3つの数abとcが与えられた場合、私たちのタスクは、与えられた数の中から最大の要素を見つけなければならないということです。 例 Input: a = 2, b = 4, c = 3 Output: 4 アルゴリズム Step 1: input three user input number. Step2: Add three numbers to list. Step 3: Using max() function to find the greatest number max(lst). Step 4: And finally we will print maximum numbe