[codeFights] almostIncreasingSequence

Given a sequence of integers as an array, determine whether it is possible to obtain a strictly increasing sequence by removing no more than one element from the array.

Example

• For sequence = [1, 3, 2, 1], the output should be
  almostIncreasingSequence(sequence) = false;
  There is no one element in this array that can be removed in order to get a strictly increasing sequence.
• For sequence = [1, 3, 2], the output should be
  almostIncreasingSequence(sequence) = true.
  You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].

Input/Output

• [execution time limit] 3 seconds (cs)
• [input] array.integer sequence
  Guaranteed constraints:
  2 ≤ sequence.length ≤ 105,
  -105 ≤ sequence[i] ≤ 105.
• [output] boolean
  Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.

So, my first thought was to calculate the longest increasing sequence for `sequence`, but it exceeded the time limit - of course, if the longest input can be 10^5, then O(n^2) algorithm should not work. One intuition is that longest increasing sequence calculates more things than we actually need. Here we can only have one element out of order, and thus decrease the difficulty of calculation.

Another note is that I start to use C# instead of python, for working purpose. My company mainly uses C#, and I want to learn.

bool almostIncreasingSequence(int[] sequence) {
    
    int leftMax = sequence[0];
    int leftMaxIndex = 0;
    int removed = 0;
    
    for(int i=1; i<sequence.Length; i++)
    {
        if(sequence[i]<=leftMax)
        {
            //need to remove leftMax
            if(removed >= 1)
                return false;
            //no items has been removed before
            if(leftMaxIndex > 0)
            {
                if (sequence[i] > sequence[leftMaxIndex-1])
                {
                    leftMax = sequence[i];
                    leftMaxIndex = i;
                }
            }
            else
            {
                leftMaxIndex = i;
                leftMax = sequence[i];
            }
            removed += 1;
        } 
        else
        {
            leftMaxIndex = i;
            leftMax = sequence[i];
        }
    }
    return true;
}