# C++ code beating 74.95% submissions with O(n) time complexity and O(1) space complexity

• class Solution {

public:

``````int maxSubArray(vector<int>& nums) {

int n = nums.size();

int numPosSA = 0; // # of contiguous positive subarrays

int numNegSA = 0; // # of contiguous negative subarrays

int PosSum = 0; // summation of a subarray starting from a pos number

int NegSum = 0; // summation of a contiguous negative subarray

int MaxPos = 0; // the largest sum of subarray if there exists at least one positive number

int MaxNeg = nums[0]; // the largest number in the array if there exists no positive number in the array

for(int i = 0; i<n; i++)

{

if(MaxNeg<nums[i])

MaxNeg = nums[i];

if(nums[i]>0)

{

PosSum += nums[i];

if(MaxPos<PosSum) //everytime there is a new positive number comming, update the sum

MaxPos = PosSum;

// A new positive subarray begin if the following holds

if(i==0)

numPosSA++;

else{

if(nums[i-1]<=0){

numPosSA++;

NegSum = 0; //everytime a new positive subarray begins, reset the negative sum

}

}

}else{

// A new negative subarray begin if the following holds

if(i==0)

numNegSA++;

else{

if(nums[i-1]>0)

{

numNegSA++;

if(MaxPos<PosSum) //save the current largest sum if necessary, since new negative subarray begins

MaxPos = PosSum;

}

}

if(numPosSA>0){ // We only count the negative sum if a previous positive subarray exists

NegSum += nums[i];

PosSum += nums[i];

PosSum = (PosSum>0)?PosSum:0;//if elements are two negative, disgard them and wait for the next positive #

}

}

}

if(MaxPos>0) // if there is at least one positive # in the array, then we have MaxPos>0, which is the final solution

return MaxPos;

else // otherwise, the solution is the largest number in the array

return MaxNeg;

}
``````

};

• The following solution uses the same idea, but is shorter and uses less variables.
As a brief explanation, the solution keeps a "sum", which is the window with maximum sum at position i. Notice that if sum drops below 0, then there's no need to keep the window running anymore, reset sum to nums[i]. If sum > 0, then including the current window certainly has a larger sum than not. Keep the maximum sum updated while iterating.

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

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.