Giả sử chúng ta có một mảng được gọi là nums và một giá trị k. Coi điểm của một mảng con (i, j) được định nghĩa là điểm tối thiểu của dãy con nums [i..j] * (j-i + 1). Bây giờ, một mảng con tốt là một mảng con trong đó i <=k <=j. Chúng ta phải tìm ra điểm tối đa có thể có của một mảng con tốt.
Vì vậy, nếu đầu vào giống như nums =[2,5,4,8,5,6] k =3, thì đầu ra sẽ là 20 vì mảng con tối ưu nằm ở đây (1,5), vì vậy tối thiểu là nums [1 ..5] là 4, do đó 4 * (5-1 + 1) =20
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ans:=nums [k], minNum:=nums [k]
-
i:=k, j:=k
-
while i> -1 or j
-
while i> -1 and nums [i]> =minNum, do
-
i:=i - 1
-
-
while j
=minNum, do -
j:=j + 1
-
-
ans:=tối đa ans và ((j - i - 1) * minNum)
-
minNum:=tối đa của (nums [i] nếu i> -1 nếu không là -1) và (nums [j] nếu j
-
-
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
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))
Đầu vào
[2,5,4,8,5,6], 3
Đầu ra
20