699.md

699. Falling Squares

Solution 1 (time O(n^2), space O(1))

class Solution(object):
    def fallingSquares(self, positions):
        """
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        n = len(positions)
        ans = [0 for _ in range(n)]
        for i, (left1, side1) in enumerate(positions):
            right1 = left1 + side1 - 1
            ans[i] = side1
            for j in range(i):
                left2, right2 = positions[j][0], positions[j][0] + positions[j][1] - 1
                if right1 >= left2 and right2 >= left1:
                    ans[i] = max(ans[i], ans[j] + side1)
        for i in range(1, n):
            ans[i] = max(ans[i], ans[i - 1])
        return ans