传送门

暴力

class Solution 
{
public:
    int maxSubArray(vector<int> &nums)
    {
        //类似寻找最大最小值的题目，初始值一定要定义成理论上的最小最大值
        int max = INT_MIN;
        int numsSize = int(nums.size());
        for (int i = 0; i < numsSize; i++)
        {
            int sum = 0;
            for (int j = i; j < numsSize; j++)
            {
                sum += nums[j];
                if (sum > max) max = sum;
            }
        }

        return max;
    }
};

DP

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int maxx = -1000000;
        for ( int i = 1; i < nums.size(); i++ ) {
            if ( nums[i-1] > 0 ) nums[i] += nums[i-1];    
        }
        for ( int i = 0; i < nums.size(); i++ ) {
            maxx = max(nums[i], maxx);
        }
        return maxx;

    }
};

class Solution
{
public:
    int maxSubArray(vector<int> &nums)
    {
        int maxx = -1000000;
        for ( int i = 1; i < nums.size(); i++ ) {
            if ( nums[i-1] > 0 ) nums[i] += nums[i-1];
            maxx = max( max(nums[i], maxx), nums[i-1] ); 
        }
        maxx = max(nums[0], maxx);
        return maxx;

    }
};

蒟蒻解法——贪心

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxsum = 0;
        int thissum = 0;
        for ( int i = 0; i < nums.size(); i++ ) {
            thissum += nums[i];
            maxsum = max( maxsum, thissum);
            if ( thissum < 0 ) thissum = 0;
        }
        if ( maxsum ) return maxsum;
        else {
            sort(nums.begin(), nums.end());
            return nums[nums.size() - 1];
        }
    }
};

分治

class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};