almostIncreasingSequence

almostIncreasingSequence.cpp

/***
* 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.
*
* Note: sequence a0, a1, ..., an is considered 
* to be a strictly increasing if 
* a0 < a1 < ... < an. Sequence containing 
* only one element is also considered to be 
* strictly increasing.
*
* Example
*
* For sequence = [1, 3, 2, 1], the output 
* should be solution(sequence) = false. There 
* is no one element in this array that can 
* be removed in order to get a strictly 
* increasing sequenc

* Return true if it is possible to remove 
* one element from the array in order to get 
* a strictly increasing sequence, otherwise 
* return false.
*/
    
#include <vector>
#include <iostream>

using namespace std;

bool solution(vector<int> sequence)
{
    const auto start = sequence.begin();
    auto curr = start;
    cons auto end = sequence.end();
    auto counter = 0;

    while (true)
    {
        const auto next = curr + 1;

        if (next == end)
            break;
        
        if (*curr < *next)
        {
            curr++;
            continue;
        }
        else
        {  // *next does not follow *curr in sequence
            if (next == end - 1 && counter == 0)
                return true;

            counter++;

            if (counter == 2)
                return false;
            
            if (curr != start && end > curr + 2 /* 2 more elements */)
            {
                const auto prev = curr - 1;
                const auto over = curr + 2;
                
                if ((*prev >= *next && *curr >= *over )|| 
                     *next >= *over)
                    return false;
                
                if (*curr >= *over && *next < *over)
                {
                    curr++;
                    continue;
                }
                else if (*curr < *over && *next < *over)
                {
                    const auto z = curr + 3;

                    if (z == end)
                    {
                        curr++;
                        continue;
                    }

                    if (*over >= *z)
                        return false;
                    else
                    {
                        curr += 3;
                        continue;
                    }
                }
            }
        }
        curr++;
    }
    return true;
}


int main()
{
    vector<int> v = {1, 2, 3, 5, 3, 6};
    cout << boolalpha << solution(v) << '\n';  // true
}