Is there any algorithm that can count the length of the longest non-decreasing contiguous subsequence with at most one substitution?
For example, given an array { 1, 7, 7, 2,3, 7, 6,-20}. Find the longest nondecreasing contiguous sequence with substitution. We can substitute any array element with any integer such as all occurrences of that element is replaced. E.g. if 7 is replaced with 1 then new array would be { 1,1,1,2,3,1,6,-20}. Only one substitution is allowed.
We know that without any substation this problem is a simple array traversal problem with O(n) time complexity. But if we have substitution options then we need to make decisions based on previous decisions. That's why it's sounds like a DP.
But the substitution can be anything. Therefore, I'm not sure how can we design the DP array.
Any idea?
