53. 最大子数组和(力扣)

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;
    }
};