Chương trình kiểm tra tổng danh sách con có lớn hơn tổng toàn bộ danh sách hay khô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 kiểm tra xem có tồn tại một danh sách con (sublist) sao cho tổng của nó lớn hơn chặt (strictly greater) tổng của toàn bộ danh sách hay không.

Ví dụ, nếu đầu vào là nums = [1, -2, 3, 4], thì đầu ra sẽ là True, vì tổng danh sách là 6 và tổng danh sách con [3, 5] là 8 lớn hơn chặt.

Để giải quyết, chúng ta thực hiện các bước sau:

• total := tổng các phần tử nums
• s := 0
• với mỗi i trong nums:
  • s := s + i
  • nếu s < 0, trả về True
• s := 0
• i := kích thước nums - 1
• trong khi i > -1:
  • s := s + nums[i]
  • nếu s < 0, trả về True
  • i := i - 1
• trả về False

Ý tưởng cốt lõi: Nếu tồn tại subarray có tổng > total_sum, thì phần còn lại (complement) sẽ có tổng < 0. Do đó chỉ cần kiểm tra xem có prefix sum hoặc suffix sum nào âm hay không.

Ví dụ

class Solution:
    def solve(self, nums):
        total = sum(nums)
        s = 0
        for i in nums:
            s += i
            if s < 0:
                return True
        s = 0
        i = len(nums) - 1
        while i > -1:
            s += nums[i]
            if s < 0:
                return True
            i -= 1
        return False

ob1 = Solution()
nums = [2, -4, 3, 5]
print(ob1.solve(nums))

Input

[2, -4, 3, 5]

Output

True