Chương trình tìm giá trị nhỏ nhất chèn đầu để tổng tiền tố đều dương trong Python

Giả sử chúng ta có một danh sách các số gọi là nums. Chúng ta phải tìm giá trị dương nhỏ nhất mà chúng ta có thể chèn vào đầu nums sao cho các tổng tiền tố của danh sách kết quả đều chứa các số lớn hơn 0.

Vì vậy, nếu đầu vào là nums = [3, -6, 4, 3], thì đầu ra sẽ là 4, vì nếu chèn 4 vào danh sách thì ta có [4, 3, -6, 4, 3]. Các tổng tiền tố lúc này là [4, 7, 1, 5, 8], tất cả đều lớn hơn 0.

Để giải quyết vấn đề này, chúng ta sẽ làm theo các bước sau:

• chèn 0 vào nums tại vị trí 0

• với i trong khoảng 1 đến kích thước nums - 1, thực hiện

  • nums[i] := nums[i] + nums[i - 1]

• trả về 1 - min(nums)

Ví dụ

Hãy xem triển khai sau để hiểu rõ hơn:

def solve(nums):
    nums.insert(0, 0)
    for i in range(1, len(nums)):
        nums[i] += nums[i - 1]
    return 1 - min(nums)

nums = [3, -6, 4, 3]
print(solve(nums))

Đầu vào

[3, -6, 4, 3]

Đầu ra

4