题目描述给你一个整数数组numsnumsnums请你找出一个具有最大和的连续子数组子数组最少包含一个元素返回其最大和。子数组是数组中的一个连续部分。示例 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算法原理这道题属于子数组问题子数组问题可以用动态规划解决一般从某一个位置为结尾或起点开始思考状态表示以iii位置为结尾dp[i]dp[i]dp[i]表示以iii位置为结尾的所有连续子数组的最大和状态转移方程以iii位置为结尾的连续子数组可以分为两类第一类是长度等于111的它的最大和是nums[i]nums[i]nums[i]第二类是长度大于111的它去掉nums[i]nums[i]nums[i]后就是以i−1i-1i−1位置为结尾的连续子数组最大和就是dp[i−1]dp[i - 1]dp[i−1]。加上nums[i]nums[i]nums[i]后它的最大和就是dp[i−1]nums[i]dp[i-1] nums[i]dp[i−1]nums[i]根据这两点可以得到dp[i]max(nums[i],dp[i−1]nums[i])dp[i] max(nums[i], dp[i - 1] nums[i])dp[i]max(nums[i],dp[i−1]nums[i])初始化多使用一个空间将dp[0]dp[0]dp[0]初始化为000。由于多了一个空间dpdpdp数组整体右移了一格填表时注意原数组下标的映射填表顺序从左到右返回值连续子数组以哪个位置为结尾都是可能的所以要返回dpdpdp数组的最大值代码classSolution{public:intmaxSubArray(vectorintnums){intnnums.size(),maxElementINT_MIN;vectorintdp(n1,0);for(inti1;in;i){dp[i]max(dp[i-1]nums[i-1],nums[i-1]);maxElementmax(dp[i],maxElement);}returnmaxElement;}};
