Increasing Sequence C++

Question

I try to solve this challenge on CodeFights, but, it doesn't work. My best solution got 25/26 (time limit exceeded on the last test) but I deleted that because I tried it yesterday (it was O(n^2)). Now I tried a new one in O(n). I am very tired and I really want to get this done today, so please help me.

Here are the statements: 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].

And here is my code until now... (poor code):

#include <iostream>
#include <vector>

#include <algorithm>

bool almostIncreasingSequence(std::vector<int> sequence) 
{
    int count = 0;


    for(int i = 0; i < sequence.size()-1; i++)
    {
        if(sequence[i] > sequence[i+1])
        {
            count++;
            sequence.erase(sequence.begin(), sequence.begin() + i);
            i--;
        }
        if(count == 2)
            return false;
    }
    return true;
}

int main()
{
    std::cout << std::endl;
    return 0;
}

Answer 1

Here is a C++11 solution with O(N) runtime:

constexpr auto Max = std::numeric_limits<std::size_t>::max();
bool is_sorted_but_skip(const std::vector<int>& vec, std::size_t index = Max){
    auto Start = index == 0 ? 1 : 0;
    auto prev = vec[Start];
    for(std::size_t i = Start + 1; i < vec.size(); i++){
        if(i == index) continue;
        if(prev >= vec[i]) return false;
        prev = vec[i];
    }
    return true;
}

bool almostIncreasingSequence(std::vector<int> v) 
{
    auto iter = std::adjacent_find(v.begin(), v.end(), [](int L, int R){ return L >= R; });
    if(is_sorted_but_skip(v, std::distance(v.begin(), iter)))
        return true;
    return is_sorted_but_skip(v, std::distance(v.begin(), std::next(iter)));
}

We use std::adjacent_find to find the first element, iter greater than or equal its next element. Then we check that sequence is strictly sorted while skipping iter's position.

Otherwise, we check that the sequence is strictly sorted while we skip iter+1's position

Worse case complexity: 3 linear scan

Demo