Increasing C ++ Sequence

Question

I am trying to solve this problem on CodeFights, but it will not work. My best solution was 25/26 (time limit exceeded in the last test), but I deleted it 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 do it today, so please help me.

Here are the instructions: Given a sequence of integers in the form of an array, determine whether it is possible to obtain a strictly increasing sequence by removing at most 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 so far ... (bad 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)));
}

std::adjacent_find, , iter . , , iter.

, , iter+1 position

: 3

Answer 2

O (N ^ 2), . i-- .

( , ), , . , , , O (1) ( 100%, std::vector).

.

Answer 3

(, ):

If you see a decrease between one element to the next, you need to delete one of them (*).

Now, what if you find two reductions between two disjoint pairs of elements? This is right :-)

With this in mind, you should solve your problem with a linear scan and a bit of constant work.

_{(*), excluding the first and last pair of elements.}