Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác pos. Chúng ta phải tìm một danh sách con A gồm các num bao gồm vị trí chỉ mục sao cho (tối thiểu là A) * (kích thước của A) là cực đại sau đó trả về giá trị.
Vì vậy, nếu đầu vào là nums =[-2, 2, 5, 4] pos =3, thì đầu ra sẽ là 8, vì danh sách con tốt nhất là [5, 4], bởi vì (5, 4) =4 và kích thước của nó là 2 chúng ta có 4 * 2 =8.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ans:=A [pos], m:=A [pos]
-
i:=pos, j:=pos
-
làm như sau cho tôi trong phạm vi từ 0 đến kích thước là A - 1, thực hiện
-
left:=A [i - 1] if i - 1> =0 if else -inf
-
right:=A [j + 1] nếu j + 1
-
nếu left> =right thì
-
i:=i - 1
-
m:=tối thiểu của m và A [i]
-
-
nếu không,
-
j:=j + 1
-
m:=tối thiểu của m và A [j]
-
-
ans:=tối đa ans và (m * (j - i + 1))
-
-
trả lại ans
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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)) Đầu vào
[-2, 2, 5, 4], 3
Đầu ra
8