1

I am a beginner for DP, and I am trying to solve one Leetcode problem - Maximum Subarray: given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum. I know there are already many DP solutions for this problem. But I want to write a DP solution myself, and I searched online about some introduction to DP. Here is the specific reference I am using: https://stackoverflow.com/a/13538715/9982458. According to this answer, the running time of the DP is O(n). Why I received the Time Limit Exceeded error with my code? Any comments will be appreciated! Thanks!

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        dp = {} # dp[i] means maxSubArray for nums[0:i] which must has A[i-1] as the end element.
        m = nums[0]
        def DP(nums):
            if len(nums) in dp: 
                return dp[len(nums)]
            else:
                if len(nums) == 1: 
                    f = nums[-1]
                else:
                    temp = DP(nums[0:-1])
                    if temp > 0:
                        f = temp + nums[-1]
                    else:
                        f = nums[-1]
                dp[len(nums)] = f
                return f
        DP(nums)
        for i in range(1, len(nums)):
            m = max(m, dp[i])
        return m
Francis
  • 189
  • 1
  • 11
  • 3
    It is correct that the running time of the dynamic programming approach is O(n). However, your implementation is O(n^2). In particular you should note that `nums[0:-1]` is not a constant-time operation, so your calls to `DP` are O(n). This can be fixed through a variety of ways. – wLui155 May 18 '21 at 19:45
  • Could you say more about that `nums[0:-1]` is not a constant-time? I didn't quite understand the difference between my `nums[0:-1]` and the `fib(n-1) + fib(n-2)` in https://stackoverflow.com/a/13538715/9982458. Why that is a constant time? – Francis May 18 '21 at 20:47
  • 1
    Your DP solution goes top-down, but ```nums[0:-1]``` requires linear time to slice the array. Try using a bottom-up DP solution – Abhinav Mathur May 18 '21 at 21:03
  • There's too much code here. This should be 5-6 lines at the most -- if you're writing more than that, maybe back up and reassess. No need for any slicing. `nums[0:-1]` is a nearly-full slice of the list, copying it element-by-element. If the list has a million elements it's going to take time proportional to that. O(1) means you can copy arbitrarily large lists in the same time it takes to copy an empty list -- clearly false. This has nothing to do with `fib(n-1) + fib(n-2)` -- it's unclear what the TC would be of that without more context (without memoization, O(2^n), with memo, O(n)). – ggorlen May 18 '21 at 21:26
  • `nums[0:-1]` *copies* `nums`, so it takes time proportional to the length of it. If you want to implement a linear-time top-down DP for this problem (which I recommend as a learning exercise, since all the implementations I ever see are all bottom-up!) in Python, I think you will need to make the inner `DP()` function a closure that does not take `nums` as a parameter, but instead relies on its ability to see the existing local variable in its parent function's scope. This function should take just an integer `endIndex` parameter, which *can* be copied in constant time. – j_random_hacker May 18 '21 at 23:06

1 Answers1

0

Now that people in the comments section have explained why your solution is slow, let me show you a much simpler solution solution to the problem:

public int maxSubArray(int[] nums) {
    int max = Integer.MIN_VALUE;
    int maxEndingHere = 0;
    for (int value : nums) {
        maxEndingHere = Math.max(0, maxEndingHere) + value;
        max = Math.max(max, maxEndingHere);
    }
    return max;
}

It works by basically checking the maximum sum subarray possible uptil that point.

Kabir Kanha Arora
  • 274
  • 4
  • 14
  • yeah, this solution is familiar to me. I'm wondering if you have some implementation of linear-time *top-down* DP for this problem? – Francis Jun 08 '21 at 16:31