一、
53. 最大子数组和 - 力扣(LeetCode)
最大子数组和,可以建立一个dp表,来存放当前的位置的累加的最大和
int maxSubArray(vector<int>& nums) {int n=nums.size();if(n==1)return nums[0];vector<int> dp(n);int sum=0;if(nums[0]>0)dp[0]=nums[0];//大于0就直接放入elsedp[0]=0;//小于0就放入0for(int i=1;i<n;i++){int sum=dp[i-1]+nums[i];if(sum>0)dp[i]=sum;else dp[i]=0;}sort(dp.begin(),dp.end());if(dp[n-1]<=0){sort(nums.begin(),nums.end());return nums[n-1];}return dp[n-1];}
二、
918. 环形子数组的最大和 - 力扣(LeetCode)
这样就是将求数组的连续最大值转换为求数组的最小值
那么我们就需要建立两个表,一个是f表,用来存最大值的,一个是g表,用来存最小值的。
int maxSubarraySumCircular(vector<int>& nums) {int n=nums.size();vector<int> f(n+1),g(n+1);//定n+1 是为了防止i-1的时候越界int fmax=INT_MIN, gmin=INT_MAX, sum=0;for(int i=1;i<=n;i++){int x=nums[i-1];f[i]=max(x,x+f[i-1]);fmax=max(fmax,f[i]);//实时读取最大值g[i]=min(x,x+g[i-1]);gmin=min(gmin,g[i]);sum+=x;}return sum==gmin?fmax:max(fmax,sum-gmin);//如果sum==gmin说明数组里全是负数}
三、
152. 乘积最大子数组 - 力扣(LeetCode)
int maxProduct(vector<int>& nums) {int len=nums.size();vector<int> pos(len);auto nag=pos;nag[0]=nums[0],pos[0]=nums[0];for(int i=1;i<len;i++){pos[i]=max(pos[i-1]*nums[i],max(nums[i],nag[i-1]*nums[i]));nag[i]=min(nag[i-1]*nums[i],min(nums[i],pos[i-1]*nums[i]));}sort(pos.begin(),pos.end());sort(nag.begin(),nag.end());return max(pos[len-1],nag[len-1]);}