https://leetcode.com/problems/maximum-subarray/

給定一個數(shù)組，找出加和最大的子數(shù)組

this problem was discussed by Jon Bentley (Sep. 1984 Vol. 27 No. 9 Communications of the ACM P885)

the paragraph below was copied from his paper (with a little modifications)

algorithm that operates on arrays: it starts at the left end (element A[1]) and scans through to the right end (element A[n]), keeping track of the maximum sum subvector seen so far. The maximum is initially A[0]. Suppose we've solved the problem for A[1 .. i - 1]; how can we extend that to A[1 .. i]? The maximum
sum in the first I elements is either the maximum sum in the first i - 1 elements (which we'll call MaxSoFar), or it is that of a subvector that ends in position i (which we'll call MaxEndingHere).

MaxEndingHere is either A[i] plus the previous MaxEndingHere, or just A[i], whichever is larger.

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxhere = nums[0];
        int maxsofar = nums[0];
        
        for(int i=1; i<nums.size(); ++i)
        {
            maxhere = (maxhere + nums[i]) > nums[i] ? (maxhere + nums[i]) : nums[i]; // 可以優(yōu)化減少一次加法
            maxsofar = maxsofar > maxhere ? maxsofar:maxhere;
        }
        return maxsofar;
    }
};

結(jié)果：
Runtime: 8 ms
Memory Usage: 7.2 MB

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int maxhere = nums[0];
        int maxsofar = nums[0];
        
        for(int i=1; i<nums.size(); ++i)
        {
            maxhere = maxhere > 0 ? (maxhere + nums[i]) : nums[i];
            maxsofar = maxsofar > maxhere ? maxsofar:maxhere;
        }
        return maxsofar;
    }
};

結(jié)果
Runtime: 4 ms, faster than 98.08% of C++ online submissions for Maximum Subarray.
Memory Usage: 7 MB, less than 100.00% of C++ online submissions for Maximum Subarray.