给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例:输入: [-2,1,-3,4,-1,2,1,-5,4],输出: 6解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。算法：动态规划。设f[i]表示以第i个元素结尾时最大子序和。
那么f[i]=max(nums[i],f[i-1]+nums[i])。即选择是否将第i个数字拼接或者以第i个数字作为开始。
class Solution { public: int maxSubArray(vector<int>& nums) { int n=nums.size(); vector<int>f(n); f[0]=nums[0]; int ans=f[0]; for(int i=1;i<n;i++){ f[i]=max(nums[i],f[i-1]+nums[i]); ans=max(ans,f[i]); } return ans; } };当然，此题还有空间复杂度为O(1)的精妙解法
class Solution { public: int maxSubArray(vector<int>& nums) { int res=INT_MIN,s=0; for(auto x:nums){ if(s<0) s=0; s+=x; res=max(res,s); } return res; } };此解法实际上是利用状态转移的性质优化了空间
转载于:https://www.cnblogs.com/programyang/p/11152773.html
相关资源：各显卡算力对照表！