Longest Increasing Subarray after add or subtract some element an amount less than K

Question

Given an array and we can add or subtract some element an amount less than K to make the longest increasing subarray

Example: An array a=[6,4,3,2] and K=1; we can subtract 1 from a[2]; add 1 to a[4] so the array will be a=[6,3,3,3] and the LIS is [3,3,3]

Answer 1

An algorithm of complexity O(n) is possible, by considering a "state" approach.

For each index i, the state corresponds to the three values that we can get: A[i]-K, A[i], A[i]+K.

Then, for a given index, for each state s = 0, 1, 2, we can calculate the maximum increasing sequence length terminating at this state.

length[i+1][s] = 1 + max (length[i][s'], if val[i][s'] <= val[i+1][s], for s' = 0, 1, 2)

We can use the fact that length[i][s] is increasing with s.

In practice, if we are only interesting to know the final maximum length, we don't need to memorize all the length values.

Here is a simple C++ implementation, to illustrate this algorithm. It only provides the maximum length.

#include <iostream>
#include <vector>
#include <array>
#include <string>

struct Status {
    std::array<int, 3> val;
    std::array<int, 3> l_seq;   // length sequences
};

int longuest_ascending_seq (const std::vector<int>& A, int K) {
    int max_length = 0;
    int n = A.size();
    if (n == 0) return 0;
    Status previous, current;
    previous = {{A[0]-K, A[0]-K, A[0]-K}, {0, 0, 0}};
    
    for (int i = 0; i < n; ++i) {
        current.val = {A[i]-K, A[i], A[i] + K};
        for (int j = 0; j < 3; ++j) {
            int x = current.val[j];
            if (x >= previous.val[2]) {
                current.l_seq[j] = previous.l_seq[2] + 1;
            } else if (x >= previous.val[1]) {
                current.l_seq[j] = previous.l_seq[1] + 1;
            } else if (x >= previous.val[0]) {
                current.l_seq[j] = previous.l_seq[0] + 1;
            } else {
                current.l_seq[j] = 1;
            }
        }
        if (current.l_seq[2] > max_length) max_length = current.l_seq[2];
        std::swap (previous, current);
    }
    return max_length;
}

int main() {
    
    std::vector<int> A = {6, 4, 3, 2, 0};
    int K = 1;
    auto ans = longuest_ascending_seq (A, K);
    std::cout << ans << std::endl;
    return 0;
}