[Python] Similar to BUY AND SELL STOCK 3, Simple DP Solution, Logic and Intuition explained.
\nclass Solution:\n    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n        ## RC ##\n        ## APPROACH : DP ##        \n\t\t## Similar to 
```\nclass Solution:\n    def minSumOfLengths(self, arr: List[int], target: int) -> int:\n        ## RC ##\n        ## APPROACH : DP ##        \n\t\t## Similar to Leetcode: 123 Best Time To Buy And Sell Stock III ##\n        ## LOGIC ##\n        ## 1. Like typical subarray sum problem, calculate the valid subarray lengths at that particular index using running/prefix sum\n        ## 2. dp will have the minimum subarray length with sum = target found till that index.\n        ## 3. now reverse the array and compute the same. (we now have both dp_left and dp_right)\n        ## 4. As there should not be any overlaps, we consider minimum found till index - 1 in left side and minimum found from this current index till end on right side. Compute the sum and store in ans.\n\t\t\n\t\t## INTUITION ## (How did I get to know that I have to use dp_left and dp_ right ?)\n\t\t## As we are finding only 2 best cases, if we consider any particular index, one best case can be to its left side , othe best case can be to its right side ##\n        \n\t\t## TIME COMPLEXICITY : O(3xN) ##\n\t\t## SPACE COMPLEXICITY : O(N) ##\n        \n        def get_sub_arrays( arr ):\n            lookup = collections.defaultdict(int)\n            running_sum = 0\n            dp = [float(\'inf\')] * len(arr)\n            \n            for i, num in enumerate(arr):\n                running_sum += num\n                if running_sum == target:\n                    dp[i] = i - 0 + 1\n                elif running_sum - target in lookup:\n                    dp[i] = i - lookup[running_sum - target] + 1\n                lookup[running_sum] = i+1\n                dp[i] = min( dp[i-1], dp[i] )\n            return dp\n        \n        dp_left = get_sub_arrays( arr )                     # from front\n        dp_right = get_sub_arrays( arr[::-1] )[::-1]        # from backwards\n        \n        ans = float(\'inf\')\n        for i in range( 1, len(arr) ):\n            ans = min( ans, dp_left[i-1] + dp_right[i] )\n        return ans if( ans != float(\'inf\') ) else -1\n```\nUPVOTE IF YOU LIKE MY SOLUTION.
['Dynamic Programming', 'Python', 'Python3']