Pythonを使用して最大の昇順サブアレイ合計を見つけるプログラム

numsと呼ばれる正の値の配列があるとすると、昇順のサブ配列の可能な最大合計をnumsで見つける必要があります。サブ配列[nums_l、nums_l + 1、...、nums_r-1、nums_r]は、l <=i

したがって、入力がnums =[15,25,35,5,15,55]のようである場合、[5,15,55]が最大合計でサブ配列を増やしているため、出力は75になります。

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

• 合計：=nums [0]

• max_total：=nums [0]

• 1からnumsのサイズの範囲のiの場合、実行します

  • nums [i]> nums [i-1]の場合、

    • 合計：=合計+ nums [i]

  • それ以外の場合

    • 合計：=nums [i]

  • total> max_totalの場合、

    • max_total：=合計

• max_totalを返す

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

例

def solve(nums):
   total=nums[0]
   max_total=nums[0]
   for i in range(1,len(nums)):
      if nums[i] > nums[i-1]:
         total+=nums[i]
      else:
         total=nums[i]
      if total > max_total:
         max_total=total
   return max_total
nums = [15,25,35,5,15,55]
print(solve(nums))

入力

[15,25,35,5,15,55]

出力

75