โปรแกรมหาผลรวม subarray เพิ่มขึ้นสูงสุดด้วย Python

สมมติว่าเรามีอาร์เรย์ nums ที่มีค่าบวก เราต้องหาผลรวมสูงสุดของ subarray ที่เพิ่มขึ้นอย่างเคร่งครัด (strictly increasing) subarray [nums_l ... nums_r] เพิ่มขึ้นได้ก็ต่อเมื่อ nums_i < nums_i+1 สำหรับทุก i ที่ l ≤ i < r

เช่น nums = [15,25,35,5,15,55] ผลลัพธ์คือ 75 เพราะ [5,15,55] เป็น subarray เพิ่มขึ้นที่มีผลรวมมากที่สุด

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

• total = nums[0], max_total = nums[0]
• วนลูป i จาก 1 ถึง len(nums)-1:
  • ถ้า nums[i] > nums[i-1]: total += nums[i] (ขยาย subarray เพิ่มขึ้น)
  • มิฉะนั้น: total = nums[i] (เริ่ม subarray ใหม่)
  • ถ้า total > max_total: max_total = total
• คืนค่า max_total

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

def solve(nums):
    total = nums[0]
    max_total = nums[0]
    for i in range(1, len(nums)):
        if nums[i] > nums[i-1]:
            total += nums[i]
        else:
            total = nums[i]
        if total > max_total:
            max_total = total
    return max_total

nums = [15,25,35,5,15,55]
print(solve(nums))

ข้อมูลเข้า

[15,25,35,5,15,55]

ข้อมูลออก

75