Chương trình tìm tổng số tối thiểu của mỗi danh sách con từ một danh sách bằng Python

Giả sử chúng ta có một danh sách các số được gọi là nums. Chúng ta phải tìm tổng nhỏ nhất của x cho mọi danh sách con x tính bằng nums. Nếu câu trả lời quá lớn, hãy sửa đổi kết quả thành 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như nums =[5, 10, 20, 10, 0], thì đầu ra sẽ là 90 bởi vì, danh sách con là [[5], [10], [20], [10], [ 0], [5,10], [10,20], [20,10], [10,0], [5,10,20], [10,20,10], [20,10,0] , [5,10,20,10], [10,20,10,0], [5,10,20,10,0]] và giá trị nhỏ nhất của chúng là [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0], vì vậy tổng là 90.

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

• ans:=0
• s:=một danh sách mới
• temp_sum:=0
• đối với mỗi chỉ mục và giá trị trong nums, hãy thực hiện
  • while s và value <=phần tử ở chỉ mục 1 của danh sách cuối cùng trong s, thực hiện
    • temp_sum:=temp_sum - phần tử ở chỉ mục 2 của danh sách cuối cùng trong s
    • xóa phần tử cuối cùng khỏi s
  • nếu s trống, thì
    • chèn một danh sách có ba phần tử [chỉ mục, giá trị, (chỉ mục + 1) * giá trị] trong s
  • nếu không,
    • chèn một danh sách có ba phần tử [chỉ mục, giá trị, (chỉ mục - phần tử đầu tiên của danh sách cuối cùng của các s) * giá trị]
  • temp_sum:=temp_sum + phần tử ở chỉ mục 2 của danh sách cuối cùng trong s
  • ans:=ans + temp_sum
• return ans mod (10 ^ 9 + 7)

Ví dụ

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

def solve(nums):
   ans = 0
   s = []
   temp_sum = 0
   for index, value in enumerate(nums):
      while s and value <= s[-1][1]:
         temp_sum -= s[-1][2]
         s.pop()
      if not s:
         s.append([index, value, (index + 1) * value])
      else:
         s.append([index, value, (index - s[-1][0]) * value])
      temp_sum += s[-1][2]
      ans += temp_sum
   return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

Đầu vào

[5, 10, 20, 10, 0]

Đầu ra

90