โปรแกรมหาผลรวมของรายการย่อย K ที่ใหญ่ที่สุดใน Python

สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งคือ k ซึ่งแทนรายการจำนวนจำนวนมากที่ต่อกัน k ครั้ง เราต้องหาผลรวมของรายการย่อยที่อยู่ติดกันโดยมีผลรวมมากที่สุด

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

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

s :=ans :=lo :=0
สำหรับค่าทั้งหมดในช่วง 0 ถึงค่าต่ำสุดของ k และ 2 ให้ทำ
- สำหรับแต่ละ x เป็น nums ทำ
  - s :=s + x
  - lo :=ขั้นต่ำของ lo, s
  - ans :=สูงสุดของ ans, s - lo
คืนค่า ans + สูงสุด 0 และผลรวมขององค์ประกอบทั้งหมดของ nums * สูงสุด 0 และ (k - 2)

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

ตัวอย่าง

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

อินพุต

[2, 4, 5, -4], 1