Я бы пошел с этим.
Редактировать: предоставляется обновленное решение. Это быстро, но читабельность не очень хорошая.
Я также включил класс main () с некоторыми стандартными последовательностями, с которыми я тестировал этот код. (В формате, который тестирующий может легко проверить, чтобы добавить дополнительные случаи).
/**
* Returns true if by removing maximum 1-entry the sequence can be strictly increasing.If not, it returns false. Doesn't check
* if sequence is empty
*/
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
int maxValue = sequence[0];
for (int i = 1; i < length; i++)
{
if (sequence[i] <= maxValue)
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
maxValue = sequence[i];
}
// else { // [i] is a local pit. Remove [i]. maxValue is not updated. }
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
else
{
maxValue = sequence[i];
}
}
return true;
}
public static void main(final String[] args)
{
final List<int[]> testInputs = new ArrayList<>();
final List<Boolean> correctResults = new ArrayList<>();
final List<Boolean> results = new ArrayList<>();
testInputs.add(new int[] { 0 }); // single-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0 }); // two-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0, 0 }); // constant sequence
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 4, 6 }); // strictly increasing
correctResults.add(true);
testInputs.add(new int[] { 3, 2, 1 }); // strictly decreasing
correctResults.add(false);
testInputs.add(new int[] { 10, 1, 2, 3 }); // first value (10) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 1 }); // last value (1) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 5, 3, 5 }); // peak (5) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 10, 4, 4, 5 }); // peak (10) followed by constant (4)
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 1, 4, 6 }); // pit (1) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 2, 6, 7 }); // pit (2) that does not recover
correctResults.add(false);
testInputs.add(new int[] { 5, 0, 3 }); // first value should be removed
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 1, 2 }); // sequence downward gap (pit)
correctResults.add(false);
for (int i = 0; i < testInputs.size(); i++)
{
results.add(checkIfRemovingMaxOneElementItIsStrictlyIncreasing_NoAssignment(testInputs.get(i)));
if (correctResults.get(i) == results.get(i))
{
System.out.println("Test case: " + i + " successful.");
}
else
{
System.out.println("Test case: " + i + " should be: " + correctResults.get(i) + " but was: " + results.get(i));
System.out.println("Test case: " + i + " input array: " + Arrays.toString(testInputs.get(i)));
}
}
}
Кроме того, если вам все равно, будет ли уничтожено определенное значение, вы можете избежать дополнительной переменной:
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing_WithoutAssignment(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
for (int i = 1; i < length; i++)
{
if (sequence[i] <= sequence[i - 1])
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
// Check if by removing [i-1] the sequence is actually increasing
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
}
else
{
// [i] is a local pit. Remove [i]
sequence[i] = sequence[i - 1];
}
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
}
return true;
}
В обеих версиях много кода внутри кода. Это правда, но они будут выполнены только в первый раз, когда последовательность обнаружит не увеличивающуюся последовательность двух последовательных значений. Так что с точки зрения производительности это должно быть хорошо.
Что касается логики:
Когда он обнаруживает, что по индексу [i]: A [i-1]> = A [i], он определяет, находится ли его после пика (таким образом, A [i-1] является «ненормально» высоким и должен быть удален из последовательность) или он находится внутри ямы (A [i] слишком низок и должен быть удален из последовательности).