กำหนด Array nums ค่าบวก หาผลรวม Subarray ความยาวคี่ทั้งหมดที่เป็นไปได้ Subarray คือ Subsequence ที่ติดกัน หาผลรวม Subarray ความยาวคี่ทั้งหมดของ nums
Input: nums = [3,8,2,5,7] → Output: 92
Odd-length Subarrays:
nums[0] = 3 nums[1] = 8 nums[2] = 2 nums[3] = 5 nums[4] = 7 nums[0..2] sum = 13 nums[1..3] sum = 15 nums[2..4] sum = 14 nums[0..4] = 25 Total = 3+8+2+5+7+13+15+14+25 = 92
ขั้นตอนการแก้ปัญหา
- total := 0
- idx := 0
- l := List ของ Odd Indices ทั้งหมด
- While idx < len(l): k = l[idx], Loop i = 0 ถึง len(nums)-1: ถ้า i+k < len(nums)+1: total += sum(nums[i:i+k]), idx += 1
- Return total
ตัวอย่าง 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
