给定一个数组arr，长度为n，最多可以删除一个连续子数组，
求剩下的数组，严格连续递增的子数组最大长度。
n <= 10^6。
动态规划+线段树。
代码用rust编写。代码如下：
use rand::Rng;
fn main() {
let n: i32 = 100;
let v: i32 = 20;
let test_time: i32 = 50000;
println!("测试开始");
for _ in 0..test_time {
let mut m = rand::thread_rng().gen_range(0, n);
if m == 0 {
m = 1;
}
let mut arr = random_array(m, v);
let ans1 = max_len1(&mut arr);
let ans2 = max_len2(&mut arr);
if ans1 != ans2 {
println!("出错了!");
break;
}
}
println!("测试结束");
}
// 暴力方法
// 为了验证
fn max_len1(arr: &mut Vec<i32>) -> i32 {
let mut ans = max(arr);
let mut n = arr.len() as i32;
for L in 0..n {
for R in L..n {
let mut cur = delete(arr, L, R);
ans = get_max(ans, max(&mut cur));
}
}
return ans;
}
fn delete(arr: &mut Vec<i32>, L: i32, R: i32) -> Vec<i32> {
let mut n = arr.len() as i32;
let mut ans: Vec<i32> = vec![];
for _ in 0..n - (R - L + 1) {
ans.push(0);
}
let mut index = 0;
for i in 0..L {
ans[index as usize] = arr[i as usize];
index += 1;
}
for i in R + 1..n {
ans[index as usize] = arr[i as usize];
index += 1;
}
return ans;
}
fn max(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
let mut ans = 1;
let mut cur = 1;
for i in 1..arr.len() as i32 {
if arr[i as usize] > arr[(i - 1) as usize] {
cur += 1;
} else {
cur = 1;
}
ans = get_max(ans, cur);
}
return ans;
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
// 正式方法
// 时间复杂度O(N*logN)
fn max_len2(arr: &mut Vec<i32>) -> i32 {
if arr.len() == 0 {
return 0;
}
let mut n = arr.len() as i32;
let mut sorted: Vec<i32> = vec![];
for _ in 0..n {
sorted.push(0);
}
for i in 0..n {
sorted[i as usize] = arr[i as usize];
}
sorted.sort();
let mut st: SegmentTree = SegmentTree::new(n);
st.update1(rank(&mut sorted, arr[0]), 1);
let mut dp: Vec<i32> = vec![];
for _ in 0..n {
dp.push(0);
}
dp[0] = 1;
let mut ans = 1;
// 一个数字也不删！长度！
let mut cur = 1;
for i in 1..n {
let mut rank0 = rank(&mut sorted, arr[i as usize]);
// (dp[i - 1] + 1)
let mut p1 = if arr[(i - 1) as usize] < arr[i as usize] {
dp[(i - 1) as usize] + 1
} else {
1
};
// // rank : 就是当前的数字
// // 1~rank-1 : 第二个信息的max
let mut p2 = if rank0 > 1 { st.max1(rank0 - 1) + 1 } else { 1 };
dp[i as usize] = get_max(p1, p2);
ans = get_max(ans, dp[i as usize]);
if arr[i as usize] > arr[(i - 1) as usize] {
cur += 1;
} else {
cur = 1;
}
// 我的当前值是rank
// 之前有没有还是rank的记录！
if st.get(rank0) < cur {
st.update1(rank0, cur);
}
}
return ans;
}
fn rank(sorted: &mut Vec<i32>, num: i32) -> i32 {
let mut l = 0;
let mut r = sorted.len() as i32 - 1;
let mut m = 0;
let mut ans = -1;
while l <= r {
m = (l + r) / 2;
if sorted[m as usize] >= num {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans + 1;
}
pub struct SegmentTree {
pub n: i32,
pub max: Vec<i32>,
pub update: Vec<i32>,
}
impl SegmentTree {
pub fn new(max_size: i32) -> Self {
let n = max_size + 1;
let mut max: Vec<i32> = vec![];
let mut update: Vec<i32> = vec![];
for _ in 0..n << 2 {
max.push(0);
update.push(-1);
}
Self { n, max, update }
}
pub fn get(&mut self, index: i32) -> i32 {
return self.max0(index, index, 1, self.n, 1);
}
pub fn update1(&mut self, index: i32, c: i32) {
self.update0(index, index, c, 1, self.n, 1);
}
pub fn max1(&mut self, right: i32) -> i32 {
return self.max0(1, right, 1, self.n, 1);
}
fn push_up(&mut self, rt: i32) {
self.max[rt as usize] = get_max(
self.max[(rt << 1) as usize],
self.max[(rt << 1 | 1) as usize],
);
}
fn push_down(&mut self, rt: i32, _ln: i32, _rn: i32) {
if self.update[rt as usize] != -1 {
self.update[(rt << 1) as usize] = self.update[rt as usize];
self.max[(rt << 1) as usize] = self.update[rt as usize];
self.update[(rt << 1 | 1) as usize] = self.update[rt as usize];
self.max[(rt << 1 | 1) as usize] = self.update[rt as usize];
self.update[rt as usize] = -1;
}
}
fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {
if ll <= l && r <= rr {
self.max[rt as usize] = cc;
self.update[rt as usize] = cc;
return;
}
let mid = (l + r) >> 1;
self.push_down(rt, mid - l + 1, r - mid);
if ll <= mid {
self.update0(ll, rr, cc, l, mid, rt << 1);
}
if rr > mid {
self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);
}
self.push_up(rt);
}
fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {
if ll <= l && r <= rr {
return self.max[rt as usize];
}
let mid = (l + r) >> 1;
self.push_down(rt, mid - l + 1, r - mid);
let mut ans = 0;
if ll <= mid {
ans = get_max(ans, self.max0(ll, rr, l, mid, rt << 1));
}
if rr > mid {
ans = get_max(ans, self.max0(ll, rr, mid + 1, r, rt << 1 | 1));
}
return ans;
}
}
// 为了测试
fn random_array(len: i32, v: i32) -> Vec<i32> {
let mut ans: Vec<i32> = vec![];
for _ in 0..len {
ans.push(rand::thread_rng().gen_range(0, v) - rand::thread_rng().gen_range(0, v));
}
return ans;
}执行结果如下：
