Chương trình tìm điểm số tối đa của good subarray trong Python

Cho mảng nums và chỉ số k. Điểm của subarray (i,j) = min(nums[i..j]) * (j-i+1). Good subarray: i ≤ k ≤ j. Tìm điểm tối đa.

Ví dụ: nums = [2,5,4,8,5,6], k = 3 → output = 20 (subarray [1..5], min=4, 4*5=20).

Giải thuật (Two pointers mở rộng từ k)

• Khởi tạo i=j=k, minNum=nums[k], ans=nums[k].
• Mở rộng i sang trái, j sang phải miễn là nums ≥ minNum.
• Cập nhật ans = max(ans, (j-i-1)*minNum).
• Cập nhật minNum = max(nums[i] nếu i≥0, nums[j] nếu j

Code Python

def solve(nums, k):
    ans = nums[k]
    minNum = nums[k]
    i = 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))  # 20

Đầu vào / Đầu ra

Input: [2,5,4,8,5,6], 3
Output: 20