Tiền tố K (K Prefix) trong Python

Cho danh sách nums và số nguyên k, tìm chỉ số i lớn nhất sao cho tổng tiền tố nums[0] + ... + nums[i] <= k. Trả về -1 nếu không tồn tại.

Ví dụ, nums = [4, -7, 5, 2, 6], k = 5, đầu ra 3 (tổng 4+(-7)+5+2 = 4 <=5, thêm 6 thì >5).

Các bước giải quyết:

• Tính tổng tiền tố tại chỗ: nums[i] += nums[i-1] cho i từ 1 đến cuối.
• Duyệt ngược từ cuối về 0: nếu nums[i] <= k, trả về i.
• Trả về -1.

Ví dụ minh họa

class Solution:
    def solve(self, nums, k):
        for i in range(1, len(nums)):
            nums[i] += nums[i-1]
        for i in range(len(nums)-1, -1, -1):
            if nums[i] <= k:
                return i
        return -1

ob = Solution()
nums = [4, -7, 5, 2, 6]
k = 5
print(ob.solve(nums, k))

Đầu vào

[4, -7, 5, 2, 6], 5

Đầu ra

3