Chương trình tìm tổng tất cả mảng con độ dài lẻ trong Python

Giả sử ta có mảng nums giá trị dương, tìm tổng tất cả mảng con (subarray) liên tiếp có độ dài lẻ.

Ví dụ: nums = [3,8,2,5,7], kết quả 92. Các mảng con độ dài lẻ:

• Độ dài 1: 3, 8, 2, 5, 7
• Độ dài 3: [3,8,2]=13, [8,2,5]=15, [2,5,7]=14
• Độ dài 5: [3,8,2,5,7]=25
• Tổng = 3+8+2+5+7+13+15+14+25 = 92

Giải thuật

1. total := 0, idx := 0
2. l := [i for i in range(len(nums)+1) if i%2!=0] (các độ dài lẻ)
3. While idx < len(l):
   • k := l[idx]
   • For i từ 0 đến len(nums)-1:
     • Nếu i+k < len(nums)+1: total += sum(nums[i:i+k])
   • idx++
4. Trả về total

Ví dụ (Python)

def solve(nums):
    total = 0
    idx = 0
    l = [i for i in range(len(nums)+1) if i % 2 != 0]
    while idx < len(l):
        k = l[idx]
        for i in range(len(nums)):
            if i + k < len(nums) + 1:
                total += sum(nums[i:i+k])
        idx += 1
    return total

nums = [3, 8, 2, 5, 7]
print(solve(nums))

Input

[3,8,2,5,7]

Output

92