Chương trình tìm tổng phạm vi của tổng mảng con được sắp xếp bằng Python

Giả sử chúng ta có một nums mảng với n phần tử dương. Nếu chúng ta tính tổng của tất cả các dãy con liền kề không rỗng của các num và sau đó sắp xếp chúng theo kiểu không giảm, bằng cách tạo một mảng mới gồm n * (n + 1) / 2 số. Chúng ta phải tìm tổng các số từ chỉ mục trái sang phải chỉ mục (1-indexed), bao gồm, trong mảng mới. Câu trả lời có thể rất lớn nên kết quả trả về modulo 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như nums =[1,5,2,6] left =1 right =5, thì đầu ra sẽ là 20 vì ở đây tất cả các tổng của mảng con là 1, 5, 2, 6, 6, 7, 8 , 8, 13, 14, nên sau khi sắp xếp, chúng là [1,2,5,6,6,7,8,8,13,14], tổng các phần tử từ chỉ số 1 đến chỉ số 5 là 1 + 5 + 2 + 6 + 6 =20.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• m:=10 ^ 9 + 7

• n:=kích thước của nums

• a:=một danh sách mới

• đối với tôi trong phạm vi từ 0 đến n - 1, hãy thực hiện

  • đối với j trong phạm vi i đến n - 1, thực hiện

    • nếu tôi giống với j, thì

      • 
        

        chèn nums [j] vào cuối một

    • nếu không,

      • insert ((nums [j] + phần tử cuối cùng của a) mod m) vào cuối

• sắp xếp danh sách một

• sm:=tổng tất cả các phần tử của một [từ chỉ mục left-1 sang phải])

• trả lại sm mod m

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

def solve(nums, left, right):
   m = 10**9 + 7
   n = len(nums)
   a=[]
   for i in range(n):
      for j in range(i,n):
         if i==j:
            a.append(nums[j])
         else:
            a.append((nums[j]+a[-1])%m)
   a.sort()
   sm=sum(a[left-1:right])
   return sm % m
nums = [1,5,2,6]
left = 1
right = 5
print(solve(nums, left, right))

Đầu vào

[1,5,2,6], 1, 5

Đầu ra

20