题目分析

从今天开始进入另一个有趣的部分——子序列相关题目，这是笔试面试中最最经典的问题之一，常用的解法是动态规划，小伙伴们一定要留心这类题目。虽然看起来难度并不大，但是遇到时可能会出现眼高手低的情况。

DP

我们使用动态规划进行求解，dp[i]表示右端点选择第i个数可得的最大值，可以得到状态转移方程
$$dp[i] = \begin{case} nums[i] + dp[i - 1] & dp[i - 1] > 0 \ nums[i] & dp[i - 1] \le 0 \end{cases}$$
当考虑到所有情况后，就可以得到右端点为任何情况下的最大值，然后求dp数组的最大值即可。DP的**时间复杂度为$O(n)$，空间复杂度为$O(n)$**。

class Solution:
    def maxSubArray(self, nums):
        lens = len(nums)
        dp = [0] * lens
        dp[0] = nums[0]
        for i in range(1, lens):
            if dp[i - 1] <= 0:
                dp[i] = nums[i]
            else:
                dp[i] = dp[i - 1] + nums[i]
        return max(dp)

优化DP

我们发现每次只需要使用到dp[i - 1]，因此可以使用一个变量pre_num保存dp[i - 1]，然后实时更新这个变量即可，并且更新同时记录最大值，这样可以节约空间复杂度。这种算法的**时间复杂度为$O(n)$，空间复杂度为$O(1)$**。

class Solution:
    def maxSubArray(self, nums):
        max_sum = pre_num = nums[0]
        for num in nums[1:]:
            if pre_num < 0:
                pre_num = 0
            pre_num += num
            max_sum = max(pre_num, max_sum)
        return max_sum

刷题总结

这个题目是一个简单的子序列问题，牛刀小试，下面来看一看其他更加精妙的题目吧。