Chương trình tìm độ dài lớn nhất mảng con có tích dương trong Python

Cho mảng nums, tìm độ dài lớn nhất của mảng con (subarray) mà tích các phần tử là dương.

Ví dụ: nums = [2,-2,-4,5,-3] cho kết quả 4 vì 4 phần tử đầu [2,-2,-4,5] có tích dương (80).

Các bước giải:

• Định nghĩa hàm phụ util(s, e) xử lý đoạn từ chỉ số s đến e.
• Đếm số phần tử âm (neg), lưu chỉ số âm đầu tiên (ns) và cuối cùng (ne).
• Nếu số âm chẵn: trả về độ dài đoạn e-s+1.
• Nếu lẻ: trả về max của e-ns (bỏ âm đầu) và ne-s (bỏ âm cuối).
• Hàm chính: chia mảng thành các đoạn không chứa 0, áp dụng util() cho từng đoạn, lấy max.

Ví dụ minh họa

def util(s, e): 
    neg = 0 
    ns, ne = -1, -1 
    for i in range(s, e+1): 
        if nums[i] < 0: 
            neg += 1 
            if ns == -1: 
                ns = i 
            ne = i 
    if neg == 0 or neg % 2 == 0: 
        return e - s + 1 
    else: 
        return max(e - ns, ne - s)  def solve(nums): 
    ans = 0 
    s, e = -1, -1 
    for i in range(len(nums)): 
        if nums[i] != 0 and s == -1: 
            s = i 
        elif nums[i] == 0 and s != -1: 
            e = i - 1 
            ans = max(ans, util(s, e)) 
            s = -1 
            e = -1 
    if s != -1 and e == -1: 
        e = len(nums) - 1 
        ans = max(ans, util(s, e)) 
    return ans  nums = [2,-2,-4,5,-3] 
print(solve(nums))

Đầu vào

[2,-2,-4,5,-3]

Đầu ra

4