โปรแกรมหาผลรวมขั้นต่ำของแต่ละรายการย่อยจากรายการใน Python

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

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[5, 10, 20, 10, 0] ดังนั้นเอาต์พุตจะเป็น 90 เพราะรายการย่อยคือ [[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]] และค่าต่ำสุดคือ [5, 10, 20, 10, 0, 5, 10, 10, 0, 5, 10, 0, 5, 0, 0] ดังนั้นผลรวมคือ 90

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

• ตอบ :=0
• s :=รายการใหม่
• temp_sum :=0
• สำหรับแต่ละดัชนีและค่าเป็น nums ทำ
  • ในขณะที่ s และ value <=องค์ประกอบที่ดัชนี 1 ของรายการสุดท้ายใน s ให้ทำ
    • temp_sum :=temp_sum - องค์ประกอบที่ดัชนี 2 ของรายการสุดท้ายใน s
    • ลบองค์ประกอบสุดท้ายออกจาก s
  • ถ้า s ว่าง ก็
    • แทรกรายการที่มีสามองค์ประกอบ [ดัชนี, ค่า, (ดัชนี + 1)*ค่า] ใน s
  • มิฉะนั้น
    • แทรกรายการที่มีสามองค์ประกอบ [ดัชนี, ค่า, (ดัชนี - องค์ประกอบแรกของรายการสุดท้ายของ s)*value]
  • temp_sum :=temp_sum + องค์ประกอบที่ดัชนี 2 ของรายการสุดท้ายใน s
  • ans :=ans + temp_sum
• ส่งคืน mod (10^9 + 7)

ตัวอย่าง

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

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))

อินพุต

[5, 10, 20, 10, 0]

ผลลัพธ์

90