โปรแกรมค้นหาผลรวม subarray สูงสุดจากน้อยไปมากโดยใช้ Python

สมมติว่าเรามีอาร์เรย์ของค่าบวกที่เรียกว่า nums เราต้องหาผลรวมสูงสุดของอาร์เรย์ย่อยจากน้อยไปมากในหน่วย nums เราสามารถพูดได้ว่า subarray [nums_l, nums_l+1, ..., nums_r-1, nums_r] กำลังขึ้นเมื่อสำหรับ i ทั้งหมด โดยที่ l <=i

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[15,25,35,5,15,55] เอาต์พุตจะเป็น 75 เนื่องจาก [5,15,55] กำลังเพิ่มอาร์เรย์ย่อยด้วยผลรวมสูงสุด

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

• รวม:=nums[0]

• max_total:=nums[0]

• สำหรับฉันในช่วง 1 ถึงขนาดของ nums ทำ

  • ถ้า nums[i]> nums[i-1] แล้ว

    • รวม :=รวม + nums[i]

  • มิฉะนั้น

    • รวม:=nums[i]

  • ถ้ารวม> max_total แล้ว

    • max_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