โปรแกรมค้นหาคะแนนสูงสุดของ subarray ที่ดีใน Python

สมมติว่าเรามีอาร์เรย์ที่เรียกว่า nums และค่า k พิจารณาคะแนนของ subarray (i, j) เป็นค่าต่ำสุดของ subarray nums[i..j] * (j-i+1) ตอนนี้ subarray ที่ดีคือ subarray โดยที่ i <=k <=j เราต้องหาคะแนนสูงสุดของ subarray ที่ดีให้ได้

ดังนั้น หากอินพุตเท่ากับ nums =[2,5,4,8,5,6] k =3 เอาต์พุตจะเป็น 20 เนื่องจากอาร์เรย์ย่อยที่เหมาะสมที่สุดอยู่ที่นี่ (1, 5) ดังนั้นค่าต่ำสุดของ nums[1 ..5] คือ 4 ดังนั้น 4*(5-1+1) =20

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

• ตอบ :=nums[k], minNum :=nums[k]

• ผม :=k, j :=k

• ในขณะที่ i> -1 หรือ j <ขนาดของ nums ทำ

  • ในขณะที่ i> -1 และ nums[i]>=minNum ทำ

    • ผม :=ผม - 1

  • ขณะที่ j <ขนาดของ nums และ nums[j]>=minNum ทำ

    • เจ :=เจ + 1

  • ans :=สูงสุดของ ans และ ((j - i - 1) * minNum)

  • minNum :=สูงสุดของ (nums[i] if i> -1 มิฉะนั้น -1) และ (nums[j] if j

• กลับมาอีกครั้ง

ตัวอย่าง

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

def solve(nums, k):
   ans = nums[k]
   minNum = nums[k]
   i = k
   j = k
   while i > -1 or j < len(nums):
      while i > -1 and nums[i] >= minNum:
         i -= 1
      while j < len(nums) and nums[j] >= minNum:
         j += 1
      ans = max(ans, (j - i - 1) * minNum)
      minNum = max(nums[i] if i > -1 else -1 , nums[j] if j <
len(nums) else -1)
   return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))

อินพุต

[2,5,4,8,5,6], 3

ผลลัพธ์

20