CODEWITHSUNDEEP
algorithmtime-complexitydynamic-programmingdivide-and-conquer
Francis
Francis

Reputation: 199

Why my DP algorithm has Time Limit Exceeded error

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

Upvotes: 1

Views: 480

Answers (1)

Kabir Kanha Arora
Kabir Kanha Arora

Reputation: 294

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.

Upvotes: 0

Related Questions