2811. Check if it is Possible to Split Array

link

I think this is the greedy way. We can make sure that whenever we just remove one element(left or right). The left array will have the maximum sum.

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        
        n = len(nums)
        
        if n <= 2:
            return True
        
        @cache
        def backtrack(i, j):
            if j - i + 1 == 2:
                return True
            if j - i + 1 < 2:
                return False
                        
            currentSum = sum(nums[i:j+1])
            
            res = False
            if currentSum - nums[i] >= m:
                res = backtrack(i+1, j)
                
            if not res and currentSum - nums[j] >= m:
                res = backtrack(i, j-1)
                
            return res

        return backtrack(0, n-1)

The tricky solution, just see if there's two adjacency elements are >= m (with what I explain above)

class Solution:
    def canSplitArray(self, nums: List[int], m: int) -> bool:
        
        n = len(nums)
        
        if n <= 2:
            return True
        
        for a, b in pairwise(nums):
            if a + b >= m:
                return True

        return False