https://leetcode.cn/problems/maximum-subarray/
1.暴力+前缀和
class Solution {
public:
int maxSubArray(vector<int>& nums) {
const int N = 1e5+10;
int sums[N];
for(int i=0;i<nums.size();i++)
if(i==0)sums[i]=nums[i];
else sums[i]=sums[i-1]+nums[i];
int maxn=-1e6+10;
for(int i=0;i<nums.size();i++)
{
for(int j=i;j<nums.size();j++)
{
int t=0;
if(i==0)t=sums[j];
else t=sums[j]-sums[i-1];
if(t>maxn)maxn=t;
}
}
return maxn;
}
};2.区间和+贪心,一旦区间和小于0直接抛弃,因为它对于以后的区间和的意义是负值
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int maxSum = nums[0];
int sum = 0;
for(int num : nums)
{
sum += num;
if(maxSum<sum)maxSum=sum;
if(sum < 0 )
sum = 0;
}
return maxSum;
}
};3.前缀和,计算好前缀和后再计算一遍1~i区间的最小前缀和,这样就可以O(n)地计算所有最大区间和了,在所有的最大区间和中取一个max即可
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<long long>sum(n+1,0);
for(int i=1;i<=n;i++)sum[i]=sum[i-1]+nums[i-1];
vector<long long>pre(n+1,0);
long long ans=-1e10;
pre[0]=sum[0];//边界条件
for(int i=1;i<=n;i++)pre[i]=min(pre[i -1],sum[i]);
for(int i=1;i<=n;i++)ans=max(ans,sum[i]-pre[i-1]);
return ans;
}
};4.线性DP,从集合角度出发分析整个问题,f[i]表示以nums[i]为结尾的最大子数组和,f[i]由以nums[i-1]为结尾的序列+nums[i] 是整数 以及 以nums[i-1]为结尾的序列+nums[i]是负数 以及 nums[i]一个数为序列三种子集组成
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int n=nums.size();
vector<int>f(n+1,0);
f[0]=nums[0];//边界条件
int res=f[0];
for(int i=1;i<n;i++)
{
f[i]=max(f[i-1]+nums[i],nums[i]);
res=max(res,f[i]);
}
return res;
}
};