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


  • 0
    H

    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;
    
    }
    

    };


  • 0
    A

    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; 
        }
    };
    

Log in to reply
 

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