পাইথনে সাবলিস্টের যোগফল পুরো লিস্টের যোগফলের চেয়ে বড় কিনা যাচাই করা

দেওয়া লিস্ট nums। এমন কোনো কন্টiguous সাবলিস্ট আছে কিনা যেন তার যোগফল পুরো লিস্টের টোটাল যোগফলের চেয়ে স্ট্রিক্টলি বড়।

উদাহরণ: [2, -4, 3, 5] → টোটাল = ৬। সাবলিস্ট [3,5] সম = ৮ > ৬ → True।

অ بَজের্ভেশন: নেগেটিভ প্রিফিক্স/সাফিক্স চেক

যদি কোনো প্রিফিক্স বা সাফিক্সের যোগফল নেগেটিভ হয়, তবে সেটি বাদ দিয়ে বাকি অংশের যোগফল টোটালের চেয়ে বড় হবে।

বাম থেকে ডানে স্ক্যান: রানিং সম s। যদি s < 0 হয় → True।
ডান থেকে বামে স্ক্যান: একইভাবে s < 0 চেক।
দুটি দিকেই নেগেটিভ না পেলে → False।

পাইথন কোড

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()
print(ob1.solve([2, -4, 3, 5]))  # True

টাইম কমপ্লেক্সিটি: O(n), স্পেস: O(1)। খুবই চমৎকার গাণিতিক ট্রিক।