Problem statement

https://binarysearch.com/problems/Number-of-Non-Overlapping-Sublists-With-Sum-of-Target/

Solution 1

Let dp(i) be the answer for the question: how many sublists we can take if we use elements upto i. Then we have two options at each moment of time:

  1. Do not take nums[i], then it is dp(i - 1).
  2. Take nums[i], then we need to find the closest index j, such that sum(nums[j:i+1]) = target. For this we can use binary search for cumulative sums.

Complexity

It is O(n log n) for time and O(n) for space.

Code

class Solution:
    def solve(self, nums, target):
        acc = [0] + list(accumulate(nums))
        d = defaultdict(list)
        for i, x in enumerate(acc):
            d[x] += [i]

        @lru_cache(None)
        def dp(i):
            if i == -1: return 0
            ans = dp(i - 1)
            sm = acc[i] - target
            if sm in d:
                idx = bisect.bisect(d[sm], i - 1)
                if idx > 0: ans = max(ans, dp(d[sm][idx - 1]) + 1)
            return ans

        return dp(len(nums))

Solution 2

Actually, no need in binary seach if we build d dictionary: the last place we seen values.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, nums, target):
        d, n = {0: 0}, len(nums)
        dp = [0] * (n + 1)
        for i, s in enumerate(accumulate(nums)):
            dp[i + 1] = dp[i]
            if s - target in d:
                dp[i + 1] = max(dp[i + 1], dp[d[s - target]] + 1)
            d[s] = i + 1
        
        return dp[-1]