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

面试题42. 连续子数组的最大和

输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

class Solution {
   public:	int maxSubArray(vector
   
    & nums) {
   		vector
    
      S;		S.reserve(nums.size());		int pos = 0;		int sum = 0;		int Max = nums[0];		int flag = 0;				for (int i = 0; i < nums.size(); i++) {
   			Max = max(Max, nums[i]);			if (nums[i] > 0) {
   				break;			}		}		if (Max <= 0)			return Max;		Max = 0;		for (int i = 0; i < nums.size(); i++) {
   			if (sum < 0) {
   				pos = i;				sum = 0;			}			Max = (Max > sum) ? Max : sum;			sum = sum + nums[i];		}		Max = (Max > sum) ? Max : sum;		return Max;	}};
    
   

分情况考虑：

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