题目描述给你一个整数数组 nums 请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例 1输入nums [-2,1,-3,4,-1,2,1,-5,4]输出6解释连续子数组 [4,-1,2,1] 的和最大为 6 。示例 2输入nums [1]输出1示例 3输入nums [5,4,-1,7,8]输出23提示1 nums.length 105-104 nums[i] 104进阶如果你已经实现复杂度为 O(n) 的解法尝试使用更为精妙的 分治法 求解。解题思路采用动态规划法DP 状态定义设 dp[i]以第 i 个元素结尾的连续子数组最大和。关键点子数组必须以 nums[i] 收尾不能断开。状态转移方程对于第 i 位有两种选择前面的子数组带上当前元素dp[i-1] nums[i]舍弃前面所有只取当前元素nums[i]取两者更大值dp[i]max(dp[i−1]nums[i], nums[i])结果怎么求dp[i] 只是以 i 结尾的最大值全局答案是整个 dp 数组里的最大值。初始条件dp[0] nums[0]第一个元素只能自己构成子数组。自己的理解重要的是理解dp[i]的含义dp[i]表示以第i个元素结尾的连续子数组最大和也就是说我以这个元素为结尾比如第三个元素那么第一、二、三元素组成的连续子数组第一、二元素组成的连续子数组和第三个元素自己组成的子数组三种情况的最大和已经被我记录下来记录成dp[2]了那么当我再来一个下一个元素nums[3],我们根本不需要考虑前面的情况我们只知道前面最大的已经被我找到了可以说把前面三个元素已经蒸馏成一个整体了。如果继续加上新来的这个nums[3]元素变得比dp[2]小不就说明nums[3]开始拖后腿以nums[3]结尾的连续子数组最大和就是它自己了代码初次编写varmaxSubArrayfunction(nums){vardpnewArray()dp[0]nums[0]maxdp[0]for(vari1;inums.length;i){dp[i]Math.max(dp[i-1]nums[i],nums[i])if(dp[i]max){maxdp[i]}}returnmax};借助AI性能优化varmaxSubArrayfunction(nums){letprenums[0];// 等价dp[i-1]只保存上一个值letmaxnums[0];for(leti1;inums.length;i){preMath.max(prenums[i],nums[i]);maxMath.max(max,pre);}returnmax;};