โปรแกรมตรวจสอบว่ามี Sublist ผลรวม > Total Sum หรือไม่ (Python)

ปัญหา

กำหนด list nums ตรวจสอบว่ามี sublist (contiguous) ที่ผลรวม > total sum ของทั้ง list หรือไม่

ตัวอย่าง: nums=[1,-2,3,4] → Total=6, Sublist [3,4] sum=7 > 6 → True

Key Insight

ถ้ามี sublist ที่ sum > total_sum → ส่วนที่เหลือ (complement) ต้องมี sum < 0
เพราะ: total = sublist_sum + rest_sum → rest_sum = total - sublist_sum < 0

ดังนั้น: ตรวจสอบว่ามี prefix sum < 0 หรือ suffix sum < 0 หรือไม่

อัลกอริทึม

1. คำนวณ total = sum(nums)
2. เช็ค Prefix sums: วนซ้าย→ขวา สะสม s, ถ้า s < 0 → True
3. เช็ค Suffix sums: วนขวา→ซ้าย สะสม s, ถ้า s < 0 → True
4. ไม่พบ → False

โค้ด Python

class Solution:
    def solve(self, nums):
        total = sum(nums)
        
        # Check prefix sums
        s = 0
        for x in nums:
            s += x
            if s < 0:
                return True
        
        # Check suffix sums
        s = 0
        for x in reversed(nums):
            s += x
            if s < 0:
                return True
        
        return False

# ทดสอบ
ob = Solution()
print(ob.solve([2, -4, 3, 5]))  # True (suffix -4+3+5=4? Wait. Let's trace)
# nums=[2,-4,3,5], total=6
# Prefix: 2, -2→True! (prefix [2,-4] sum=-2 < 0)
# So sublist [3,5] sum=8 > 6

print(ob.solve([1, 2, 3]))      # False (all positive)
print(ob.solve([-1, -2, -3]))   # True (prefix -1 < 0)
print(ob.solve([5, -2, -2]))    # True (suffix -2-2=-4 < 0, sublist [5] sum=5 > 1)

ความซับซ้อน

• Time: O(n)
• Space: O(1)

การพิสูจน์

Let total = S, sublist sum = X > S
Rest sum = S - X < 0
Rest คือ prefix หรือ suffix ของ sublist (เพราะ sublist เป็น contiguous)
ดังนั้น ถ้ามี prefix/suffix sum < 0 → ตอบ True
Conversely: ถ้ามี prefix sum < 0 → sublist = complement มี sum > S

Edge Cases

• All positive → False (prefix/suffix sums ไม่มี negative)
• All negative → True (prefix sum ตัวแรก negative)
• Single element → False (no proper sublist)