สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกค่าหนึ่งเป็น pos เราต้องหารายการย่อย A ของ nums ที่มีดัชนี pos ที่ (ขั้นต่ำของ A) * (ขนาด A) ถูกขยายให้ใหญ่สุดแล้วคืนค่ากลับ
ดังนั้น หากอินพุตเท่ากับ nums =[-2, 2, 5, 4] pos =3 เอาต์พุตจะเป็น 8 เนื่องจากรายการย่อยที่ดีที่สุดคือ [5, 4] เพราะ (5, 4) =4 และ ขนาดของมันคือ 2 เรามี 4 * 2 =8
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ans :=A[pos], m :=A[pos]
-
ผม :=pos, j :=pos
-
ทำสิ่งต่อไปนี้สำหรับ i ในช่วง 0 ถึงขนาด A - 1 ทำ
-
left :=A[i - 1] if i - 1>=0 มิฉะนั้น -inf
-
right :=A[j + 1] if j + 1
-
ถ้าซ้าย>=ขวา แล้ว
-
ผม :=ผม - 1
-
m :=ขั้นต่ำของ m และ A[i]
-
-
มิฉะนั้น
-
เจ :=เจ + 1
-
m :=ขั้นต่ำของ m และ A[j]
-
-
ans :=สูงสุดของ ans และ (m *(j - i + 1))
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution:
def solve(self, A, pos):
NINF = float("-inf")
ans = m = A[pos]
i = pos
j = pos
for _ in range(len(A) - 1):
left = A[i - 1] if i - 1 >= 0 else NINF
right = A[j + 1] if j + 1 < len(A) else NINF
if left >= right:
i -= 1
m = min(m, A[i])
else:
j += 1
m = min(m, A[j])
ans = max(ans, m * (j - i + 1))
return ans
ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos)) อินพุต
[-2, 2, 5, 4], 3
ผลลัพธ์
8
