Intuition

l <= size <= r 길이의 부분원소의 합이 0보다 큰 가장 작은 합을 도출
정답이 없을 시 -1 출력

Approach

• 브루트포스로 접근 가능하지만, prefix_sum을 활용하면 더 효율적으로 풀 수 있음.
• 각 인덱스까지의 합을 저장하는 prefix_sum 생성(0번 인덱스는 0으로 놓기!)
• l~r까지 순회하며 prefix_sum에서 부분합을 바로 확인
• 조건에 따라 answer를 계속 업데이트 해주며 최종적으로 출력

Complexity

• Time complexity: $O(n)$

• Space complexity: $O(n)$

Code

class Solution:
    def minimumSumSubarray(self, nums: List[int], l: int, r: int) -> int:
        n = len(nums)
        # prefix sums
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i+1] = pre[i] + nums[i]

        answer = inf

        # check all lengths
        for length in range(l, r+1):
            for i in range(n - length + 1):
                s = pre[i+length] - pre[i]
                if s > 0:
                    answer = s if s<answer else answer
                    
        #for ws in range(l,r+1):
        #    for i in range(n-ws+1):
        #        s = sum(nums[i:i+ws])
        #        if s > 0: 
        #            answer = min(answer, s)
         
        return answer if answer != float('inf') else -1