โปรแกรมหาผลรวมความกว้างของลำดับย่อยทั้งหมดของรายการตัวเลขในPython

สมมติว่าเรามีรายการของตัวเลขที่เรียกว่า nums ความกว้างของลำดับของตัวเลขเป็นความแตกต่างระหว่างจำนวนสูงสุดและต่ำสุดในลำดับ เราต้องหาผลรวมของความกว้างของลำดับย่อยทั้งหมดของ nums หากคำตอบมีขนาดใหญ่มาก ให้แก้ไขผลลัพธ์ 10^9+7

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[7, 4, 9] ผลลัพธ์จะเป็น 15 เนื่องจากเรามีลำดับย่อยเช่น [7], [4], [9], [7, 4], [ 7, 9], [4, 9], [7, 4, 9] และความกว้างคือ 0, 0, 0, 3, 2, 5, 5 ได้ 15

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ม :=10^9 + 7

• เรียงเลขรายการ

• ตอบ :=0

• power :=รายการขนาดเท่ากับ (nums + 1) และเติมด้วย 1

• สำหรับฉันอยู่ในช่วง 1 ถึงขนาด nums + 1 ทำ

  • power[i] :=power[i - 1] * 2 mod m

  • สำหรับฉันในช่วง 0 ถึงขนาดของ nums ทำ

    • บวก :=(กำลัง[i] - 1) * nums[i]

    • เชิงลบ :=(กำลัง[ขนาดของ nums - i - 1] - 1) * nums[i]

    • ans :=(ans + positive - negative) mod m

• กลับมาอีกครั้ง

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

class Solution:
   def solve(self, nums):
      m = 10**9 + 7
      nums.sort()
      ans = 0
      power = [1] * (len(nums) + 1)
      for i in range(1, len(nums) + 1):
         power[i] = power[i - 1] * 2 % m
      for i in range(0, len(nums)):
         positive = (power[i] - 1) * nums[i]
         negative = (power[len(nums) - i - 1] - 1) * nums[i]
         ans = (ans + positive - negative) % m
      return ans
ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

อินพุต

[7, 4, 9]

ผลลัพธ์

15