Solved by processing the input vector 3 times. Run time is 65ms


  • 0
    I

    class Solution
    {
    private:

    int m_vecSize = 0;
    

    public:

    int maxSubArray(vector<int>& nums)
    {
    
    	//If vector is empty, then return 0.
    	if (nums.empty())
    	{
    		return 0;
    	}
    
    	m_vecSize = nums.size();
    
    	//If vector only contains 1 element, then return that element.
    	if (m_vecSize == 1)
    	{
    		return nums.at(0);
    	}
    
    	//If the vector contains only negative numbers (and 0), return the largest number in the vector.
    	if (!IsPositiveNumberInVector(nums))
    	{
    		return FindLargestInVector(nums);
    	}
    
    	vector<int> newNums;
    	
    	//We should have a new vector newNums containing alternating positive and negative numbers
    	//with positive numbers on its edges.
    	ProcessInputVector(nums, newNums);
    
    	bool squeezed = true;
    	while (squeezed)
    	{
    		if (m_vecSize <= 2)
    		{
    			return ForVecsizeLessThanTwo(newNums);
    		}
    
    		squeezed = SqueezeCenterNumberPositive(newNums);
    	}
    
    	//Before we process the vector further by squeezing out the positive numbers too,
    	//we want to keep track of what our largest number in the vector is because if this largest number
    	//is what we are looking for, {10, -100, 50, -100, 10}, we will lose it if we squeeze it out.
    	//However, if we don't further squeeze out the positive numbers, we may not get the max sum.
    	//e.g. {100, -20, 10, -20, 100} -> {100, -30, 100} -> {170}
    	int largestAfterSqueezePositive = FindLargestInVector(newNums);
    
    	squeezed = true;
    	while (squeezed)
    	{
    		if (m_vecSize <= 2)
    		{
    			return ForVecsizeLessThanTwo(newNums);
    		}
    
    		squeezed = SqueezeCenterNumber(newNums);
    	}
    
    	int largestAfterSqueezeNegative = FindLargestInVector(newNums);
    
    	return BiggerOfTheTwo(largestAfterSqueezePositive, largestAfterSqueezeNegative);
    }
    
    //At this point, we are guaranteed 1 positive number in the vector.
    //Process input ignores negative numbers at the edges
    //Then sum the same-signed integers adjacent to each other.
    //newNums will contain alternating positive and negative numbers with positive numbers on the edges
    //+-+-+-.....-+-+-+
    void ProcessInputVector(vector<int>& nums, vector<int>& newNums)
    {
    	int startingIndex = GetStartingIndex(nums);
    
    	newNums.push_back(nums.at(startingIndex));
    	int isCurrentPositive = true;
    	int isNextPositive = false;
    	for (int j = startingIndex + 1; j < m_vecSize; ++j)
    	{
    		isNextPositive = IsPositive(nums.at(j));
    		if (isCurrentPositive == isNextPositive)
    		{
    			newNums.back() += nums.at(j);
    		}
    		else
    		{
    			newNums.push_back(nums.at(j));
    			isCurrentPositive = isNextPositive;
    		}
    	}
    
    	//Now we keep track of vector size for newNums.
    	m_vecSize = newNums.size();
    
    	return;
    }
    
    //Return the first index where the positive number occurs.
    int GetStartingIndex(vector<int>& nums)
    {
    	int positiveNumIndex = 0;
    	for (positiveNumIndex; positiveNumIndex < m_vecSize; ++positiveNumIndex)
    	{
    		if (IsPositive(nums.at(positiveNumIndex)))
    		{
    			break;
    		}
    	}
    
    	for (m_vecSize; m_vecSize >= positiveNumIndex + 1; --m_vecSize)
    	{
    		if (IsPositive(nums.at(m_vecSize - 1)))
    		{
    			break;
    		}
    	}
    
    	return positiveNumIndex;
    }
    
    //Returns true if there's a positive number in the vector
    bool IsPositiveNumberInVector(vector<int>& nums)
    {
    	for (vector<int>::iterator it = nums.begin(); it != nums.end(); ++it)
    	{
    		if (IsPositive(*it))
    		{
    			return true;
    		}
    	}
    
    	return false;
    }
    
    //Further process the vector by squeezing out the negative numbers if its neighbors are both bigger
    //than the abs() of the negative number. ...10, -5, 12... -> ...17...
    //Either direction we go (towards the left or right) we can be sure the total sum will always be bigger.
    bool SqueezeCenterNumberPositive(vector<int>& nums)
    {
    	bool squeezed = false;
    
    	int absCenterNumber = 0;
    	for (int i = m_vecSize - 1; i >= 2; i -= 2)
    	{
    		absCenterNumber = Abs(nums.at(i - 1));
    		if (nums.at(i) >= absCenterNumber && nums.at(i - 2) >= absCenterNumber)
    		{
    			squeezed = true;
    			nums.at(i - 2) += nums.at(i) + nums.at(i - 1);
    			RemoveElement(nums, i);
    			RemoveElement(nums, i - 1);
    		}
    	}
    
    	return squeezed;
    }
    
    //Further process the vector by squeezing out both positive and negative numbers if the abs() of its neighbors
    //are both bigger than the abs() of the squeezed number.
    bool SqueezeCenterNumber(vector<int>& nums)
    {
    	bool squeezed = false;
    
    	int absLeftNumber = 0;
    	int absCenterNumber = 0;
    	int absRightNumber = 0;
    	for (int i = m_vecSize - 1; i >= 2; --i)
    	{
    		absLeftNumber = Abs(nums.at(i));
    		absCenterNumber = Abs(nums.at(i - 1));
    		absRightNumber = Abs(nums.at(i - 2));
    		if (absLeftNumber >= absCenterNumber && absRightNumber >= absCenterNumber)
    		{
    			squeezed = true;
    			nums.at(i - 2) += nums.at(i) + nums.at(i - 1);
    			RemoveElement(nums, i);
    			RemoveElement(nums, i - 1);
    			i--;
    		}
    	}
    
    	return squeezed;
    }
    
    bool IsPositive(int num)
    {
    	if (num > 0)
    	{
    		return true;
    	}
    
    	return false;
    }
    
    int Abs(int num)
    {
    	if (num < 0)
    	{
    		return -num;
    	}
    
    	return num;
    }
    
    void RemoveElement(vector<int>& nums, int index)
    {
    	for (int i = index; i < m_vecSize - 1; ++i)
    	{
    		nums.at(i) = nums.at(i + 1);
    	}
    
    	nums.pop_back();
    	m_vecSize--;
    
    	return;
    }
    
    int BiggerOfTheTwo(int a, int b)
    {
    	if (a > b)
    	{
    		return a;
    	}
    
    	return b;
    }
    
    int ForVecsizeLessThanTwo(vector<int>& nums)
    {
    	if (m_vecSize == 1)
    	{
    		return nums.at(0);
    	}
    
    	if (m_vecSize == 2)
    	{
    		return BiggerOfTheTwo(nums.at(0), nums.at(1));
    	}
    
    	return 0;
    }
    
    int FindLargestInVector(vector<int>& nums)
    {
    	int largest = nums.at(0);
    
    	for (vector<int>::iterator it = nums.begin() + 1; it != nums.end(); ++it)
    	{
    		if (*it >= largest)
    		{
    			largest = *it;
    		}
    	}
    
    	return largest;
    }
    

    };


Log in to reply
 

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