Pythonで配列を3つのサブ配列に分割する方法の数を見つけるためのプログラム

numsという配列があるとすると、この配列numsを分割するための適切な方法をいくつか見つける必要があります。答えが大きすぎる可能性があるため、10 ^ 9 + 7を法とする結果を返します。ここで、配列を左から右にそれぞれ3つの空でない連続したサブ配列に分割し、その合計が左側の要素は中央部分の要素の合計以下であり、中央部分の要素の合計は右側の要素の合計以下です。

したがって、入力がnums =[2,3,3,3,7,1]のようである場合、分割には3つの異なる方法があるため、出力は3になります。

• [2]、[3]、[3,3,7,1]
• [2]、[3,3]、[3,7,1]
• [2,3]、[3,3]、[7,1]

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

• n：=numsのサイズ、
• m：=10 ^ 9 + 7
• ss：=サイズ（1 + n）の配列で、0で埋めます
• インデックスiと値val（nums）ごとに、do
  • ss [i]：=ss [i-1] + val
• r：=0、rr：=0、ans：=0
• 1からn-2の範囲のlについては、
  • r：=rとl+1の最大値
  • r
  • r：=r + 1
• rr：=rrとrの最大値
• rr =ss [rr + 1]-ss [l]の場合、do
  • rr：=rr + 1
• ss [l]> ss [r]-ss [l]の場合、
  • ループから抜け出す
• ss [r]-ss [l]> ss [n]-ss [r]の場合、
  • 次の反復に進む
• ans：=（ans + rr --r + 1）mod m

例

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

def solve(nums):
   n, m = len(nums), 10**9+7
   ss = [0] * (1+n)
   for i, val in enumerate(nums, 1):
      ss[i] = ss[i-1] + val

   r = rr = ans = 0
   for l in range(1, n-1):
      r = max(r, l+1)
      while r < n-1 and ss[r]-ss[l] < ss[l]:
         r += 1
      rr = max(rr, r)
      while rr < n-1 and ss[n]-ss[rr+1] >= ss[rr+1]-ss[l]:
         rr += 1
      if ss[l] > ss[r]-ss[l]:
         break
      if ss[r]-ss[l] > ss[n]-ss[r]:
         continue
      ans = (ans+rr-r+1) % m
   return ans

nums = [2,3,3,3,7,1]
print(solve(nums))

入力

[1,7,3,6,5]

出力

3