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

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

};

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