本文共 910 字，大约阅读时间需要 3 分钟。

class Solution {//OJ suggest to solve this problem using D&C, but its time complexity is O(nlogn), right?//So I choose the O(n) version to implementpublic:	int maxSubArray(int A[], int n) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		if(0 == n) return 0;		int ans = A[0];		int local = 0;		for (int i = 0; i < n; ++i)		{			local = local > 0 ? local+A[i] : A[i];			ans = max(local, ans);		}		return ans;	}};

second time

class Solution {public:    int maxSubArray(int A[], int n) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        if(n == 0) return 0;        int curSum = A[0];        int maxSum = curSum;        for(int i = 1; i < n; ++i)        {            if(curSum+A[i] > A[i]) curSum = curSum+A[i];            else curSum = A[i];            maxSum = max(maxSum, curSum);        }                return maxSum;        }};

转载地址：http://olxti.baihongyu.com/