โปรแกรมค้นหาผลรวมสูงสุดของรายการย่อยแบบวงกลมใน Python

สมมติว่าเรามีรายการตัวเลข ตอนนี้ ให้พิจารณารายการหมายเลขแบบวงกลมที่จุดเริ่มต้นและจุดสิ้นสุดของหมายเลขเป็นเพื่อนบ้าน เราต้องหาผลรวมสูงสุดของรายการย่อยที่ไม่ว่างในรายการแบบวงกลม

ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[2, 3, -7, 4, 5] ผลลัพธ์จะเป็น 14 เนื่องจากเราสามารถหารายการย่อย [4, 5, 2, 3] ซึ่งรวมเป็น 14

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

• max_sum :=ลบอินฟินิตี้, cur_max :=0

• min_sum :=อินฟินิตี้บวก, cur_min :=0

• สำหรับแต่ละ num เป็น num ทำ

  • cur_max :=สูงสุดของ num และ cur_max + num

  • max_sum :=สูงสุดของ max_sum และ cur_max

  • cur_min :=ขั้นต่ำ num และ cur_min + num

  • min_sum :=ขั้นต่ำของ min_sum และ cur_min

• ถ้า max_sum <=0 แล้ว

  • คืนค่า max_sum

• คืนค่าสูงสุดของ max_sum และ (ผลรวมขององค์ประกอบทั้งหมดเป็น nums - min_sum)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

import math
class Solution:
   def solve(self, nums):
      max_sum = -math.inf
      cur_max = 0
      min_sum = math.inf
      cur_min = 0
      for num in nums:
         cur_max = max(num, cur_max + num)
         max_sum = max(max_sum, cur_max)
         cur_min = min(num, cur_min + num)
         min_sum = min(min_sum, cur_min)
      if max_sum <= 0:
         return max_sum
      return max(max_sum, sum(nums) - min_sum)
ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))

อินพุต

[2, 3, -7, 4, 5]

ผลลัพธ์

14