为什么我的DP算法有时间限制超过错误

Question

我是DP的初学者，我正在尝试解决一个Leetcode问题-最大子数组：给定一个整数数组nums，找到具有最大和的连续子数组（至少包含一个数字），并返回其和。我知道这个问题已经有很多DP解决方案。但我想自己写一个DP解决方案，我在网上搜索了一些关于DP的介绍。以下是我使用的具体参考资料：https://stackoverflow.com/a/13538715/9982458.根据该答案，DP的运行时间为O（n）。为什么我收到代码超过时间限制的错误？如有任何意见，将不胜感激！谢谢

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

Answer 1

既然评论部分的人已经解释了为什么你的解决方案很慢，让我向你展示一个更简单的解决方案：

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;
}

它的工作原理基本上是检查该点上可能出现的最大和子阵列。