Cho một dãy số nguyên dưới dạng một mảng, hãy xác định xem liệu có thể có được một dãy số tăng dần hay không bằng cách loại bỏ không quá một phần tử khỏi mảng.
Dãy a0, a1, ..., an được coi là tăng nghiêm ngặt nếu a0
Đối với chuỗi =[1, 3, 2, 1], đầu ra phải là -
Không có một phần tử nào trong mảng này có thể bị xóa để có được một chuỗi tăng dần.
Đối với trình tự =[1, 3, 2], đầu ra phải là -
Chúng ta có thể loại bỏ 3 khỏi mảng để nhận được dãy tăng dần [1, 2]. Ngoài ra, chúng ta có thể loại bỏ 2 để có được chuỗi tăng dần [1, 3].
Sau đây là mã -
Điều này sẽ tạo ra kết quả sau trên bảng điều khiển - Ví dụ
almostIncreasingSequence(sequence) = false.
almostIncreasingSequence(sequence) = true.
Ví dụ
const arr1 = [3, 5, 67, 98, 3];
const arr2 = [4, 3, 5, 67, 98, 3];
const almostIncreasingSequence = sequence => {
let removed = 0;
let i = 0;
let prev = -Infinity;
while(removed < 2 && i < sequence.length) {
if(sequence[i] > prev) {
prev = sequence[i];
}else{
prev = Math.min(prev, sequence[i]);
removed++;
}
i++;
}
return removed < 2;
};
console.log(almostIncreasingSequence(arr1));
console.log(almostIncreasingSequence(arr2)); Đầu ra
true
false