Pythonのサブ配列の最大絶対和を見つけるプログラム

numsという配列があるとします。サブ配列[nums_l、nums_l + 1、...、nums_r-1、nums_r]の絶対和は| nums_l + nums_l + 1 + ... + nums_r-1 +nums_r|である必要があります。 numsのサブ配列の最大絶対合計を見つける必要があります（そのサブ配列は空である可能性があります）。

したがって、入力がnums =[2、-4、-3,2、-6]の場合、サブ配列[2、-4、-3,2]の絶対サブ配列の合計は最大であるため、出力は11になります。 2 +（-4）+（-3）+ 2 | =11.

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

• n：=numsのサイズ

• ans：=0、temp：=0

• 0からn-1の範囲のiの場合、実行

  • temp <0の場合、

    • temp：=0

  • temp：=temp + nums [i]

  • ans：=ansと|temp |

    の最大値

• temp：=0

• 0からn-1の範囲のiの場合、実行

  • temp> 0の場合、

    • temp：=0

  • temp：=temp + nums [i]

  • ans：=ansと|temp |

    の最大値

• ansを返す

例

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

def solve(nums):
   n=len(nums)
   ans=0
   temp=0

   for i in range(n):
      if (temp<0):
         temp=0
   temp=temp+nums[i]
   ans=max(ans,abs(temp))

   temp=0
   for i in range(n):
      if (temp>0):
         temp=0
      temp=temp+nums[i]
      ans=max(ans,abs(temp))

   return ans

nums = [2,-4,-3,2,-6]
print(solve(nums))

入力

[2,-4,-3,2,-6]

出力

11