BinarySearch 0261 Sublist Sum

Problem statement

https://binarysearch.com/problems/Sublist-Sum/

Solution

Variation of Leetcode 0053. Maximum Subarray.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums):
        if not nums: return False
        dp = [0]*len(nums)
        dp[0] = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], nums[i] + dp[i-1])
        return max(max(dp), 0) > sum(nums)