โปรแกรมหาผลรวมของ subarray sums ที่เรียงแล้วในช่วงที่กำหนดด้วย Python

สมมติว่าเรามีอาร์เรย์ nums ขนาด n ที่มีค่าบวกทั้งหมด หากเราคำนวณผลรวมของทุก subarray ที่ติดกันและไม่ว่าง แล้วเรียงลำดับจากน้อยไปมาก จะได้อาร์เรย์ใหม่ขนาด n(n+1)/2 เราต้องหาผลรวมของค่าตั้งแต่ index left ถึง right (1-indexed) รวมทั้งสองข้าง ผลลัพธ์อาจใหญ่มาก จึงต้อง modulo 10⁹ + 7

เช่น ถ้าข้อมูลเข้าเป็น nums = [1,5,2,6] left = 1 right = 5 ผลลัพธ์จะเป็น 20 เพราะ subarray sums ทั้งหมดคือ 1, 5, 2, 6, 6, 7, 8, 8, 13, 14 หลังเรียงแล้วได้ [1,2,5,6,6,7,8,8,13,14] ผลรวม index 1 ถึง 5 คือ 1+5+2+6+6 = 20

ขั้นตอนการแก้ปัญหา

• กำหนด m = 10⁹ + 7
• n = ขนาดของ nums
• สร้างลิสต์ a ว่าง
• วนลูป i จาก 0 ถึง n-1:
  • วนลูป j จาก i ถึง n-1:
    • ถ้า i == j ให้เพิ่ม nums[j] เข้า a
    • มิฉะนั้น ให้เพิ่ม (nums[j] + a[-1]) % m เข้า a
• เรียงลำดับ a
• sm = ผลรวม a[left-1:right]
• คืนค่า sm % m

ตัวอย่างโค้ด

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

ข้อมูลเข้า

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

ข้อมูลออก

20