Challenge 4
Page 1 of 1
Challenge 4
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.
Example
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
Input/Output
[time limit] 3000ms (java)
[input] array.integer sequence
Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.
[output] boolean
Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.
Example
For sequence = [1, 3, 2, 1], the output should be
almostIncreasingSequence(sequence) = false;
There is no one element in this array that can be removed in order to get a strictly increasing sequence.
For sequence = [1, 3, 2], the output should be
almostIncreasingSequence(sequence) = true.
You can remove 3 from the array to get the strictly increasing sequence [1, 2]. Alternately, you can remove 2 to get the strictly increasing sequence [1, 3].
Input/Output
[time limit] 3000ms (java)
[input] array.integer sequence
Guaranteed constraints:
2 ≤ sequence.length ≤ 105,
-105 ≤ sequence[i] ≤ 105.
[output] boolean
Return true if it is possible to remove one element from the array in order to get a strictly increasing sequence, otherwise return false.
Re: Challenge 4
boolean almostIncreasingSequence(int[] sequence) {
for (int erasedIndex = 0; erasedIndex < sequence.length; erasedIndex++)
{
boolean ans = true;
int last = 0, start = 1;
if (erasedIndex == 0) {
last = 1;
start = 2;
}
for (int j = start; j < sequence.length; ++j) {
if (j == erasedIndex) {
continue;
}
if (sequence[j] <= sequence[last]) {
ans = false;
break;
}
last = j;
}
if (ans) {
return true;
}
}
return false;
}
for (int erasedIndex = 0; erasedIndex < sequence.length; erasedIndex++)
{
boolean ans = true;
int last = 0, start = 1;
if (erasedIndex == 0) {
last = 1;
start = 2;
}
for (int j = start; j < sequence.length; ++j) {
if (j == erasedIndex) {
continue;
}
if (sequence[j] <= sequence[last]) {
ans = false;
break;
}
last = j;
}
if (ans) {
return true;
}
}
return false;
}
Page 1 of 1
Permissions in this forum:
You cannot reply to topics in this forum
|
|