関数名を変更 (push→insert)

q060.rs

const MAX: i32 = std::i32::MAX;

struct LIS {
    n: usize,
    data: Vec<i32>,
}
impl LIS {
    fn new(n: usize) -> Self {
        Self { n, data: vec![MAX; n], }
    }
    // 数列内にxがなければ挿入した後に、xまでの要素数を返す
    fn insert(&mut self, x: i32) -> usize {
        let pos = self.data.binary_search(&x);
        match pos {
            Ok(pos) => { pos+1 },
            Err(pos) => { self.data[pos] = x; pos+1 },
        }
    }
}

fn main() {
// Step #1. 入力
    proconio::input! { n: usize, a: [i32; n], };

// Step #2. 左側の LIS を求める
    let mut left = vec![0; n];
    let mut lis = LIS::new(n);
    for (i, &ai) in a.iter().enumerate() {
        left[i] = lis.insert(ai);
    }

// Step #3. 右側の LIS を求める
    let mut right = vec![0; n];
    let mut lis = LIS::new(n);
    for (i, &ai) in a.iter().enumerate().rev() {
        right[i] = lis.insert(ai);
    }

// Step #4. 答えを求める
    let ans = (0..n).map(|i| left[i]+right[i]-1 ).max().unwrap();
    println!("{}", ans);
}