Obtaining strictly increasing sequence in array?-CodePudding

I am working on this algorithm problem,

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.

I am not sure how to proceed with this?

CodePudding user response：

Hints:

The "strictly increasing" property breaks when an element is immediately followed by a non-larger element. You can detect such a configuration by a simple linear search (and there is no faster way).

Now there are two ways to fix: by removing one of the elements, or the other. Ask yourself if the two choices are equivalent.

Next you need to check that after removal no more inversions exist (by continuing the search from the right point).

CodePudding user response：

The problem is a LeetCode #1909

We can easily check if array is increasing with one item removed, e.g. (c# code):

    // if nums is sorted except the item at indexToRemove
    public bool IsSorted(int[] nums, int indexToRemove) {
        if (nums.Length <= 1)
            return true;
        
        int prior = 0;
        bool hasPrior = false;
        
        for (int i = 0; i < nums.Length;   i) {
            if (i == indexToRemove) // don't count for item at indexToRemove
                continue;
            
            if (!hasPrior) 
                hasPrior = true;
            else if (prior >= nums[i])
                return false;
            
            prior = nums[i];
        }
        
        return true;
    }

Then we can scan the array, and if we have conflict, i.e. array[i - 1] >= array[i] we can try to remove either i-1th or ith item and check if we have an strictly increasing sequence:

    public bool CanBeIncreasing(int[] nums) {
        if (nums.Length <= 2)
            return true;
        
        for (int i = 1; i < nums.Length;   i) {
            if (nums[i - 1] < nums[i]) // no conflict, keep on doing
                continue;
                     
            // conflict; can we resolve it removing item #i - 1 or item #i? 
            return IsSorted(nums, i - 1) || IsSorted(nums, i);
        }
        
        // no conflicts at all, we don't need to remove any item  
        return true;
    }