ALDS1 D_1
$ O(n^2) での方法:
総当たりで引き算を行う
index:1 とindex:0、index:2とindex:0、index:2とindex:1、index:3とindex:0……
外側forで扱うindexの値$ \le 内側forで扱うindexの値になったらcontinueする
今迄の値と引き算の値を比較して引き算の値のほうが大きければreplaceする
TLEになった
$ n = 10000では耐えたが $ n \simeq 200000 では厳しいらしい
code:rust
fn main() {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let n = s.trim().parse::<usize>().unwrap();
let mut arr: Vec<i64> = Vec::new();
for _i in 1..=n {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let st = s.trim();
arr.push(st.parse::<i64>().unwrap());
}
let mut max_value = -1000000000;
for i in 1..n {
for j in 0..n {
if i <= j { continue; }
//println!("{2}x{3}: {0} < {1}", max_value, sub, i, j);
if max_value < sub {
max_value = sub;
}
}
}
println!("{}",max_value);
}
上の場合におけるiとjには$ i < jの関係がある
最大となる落差における始点は$ jより前に 必ず存在していなければならない
つまり、$ jより前に 存在する最小の値と$ jを比較すればよい
$ jより前に 存在する最小の値は変数として保持すれば $ O(1)で参照が可能である
この手法では$ O(n)で求められる
code:rust
fn main() {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let n = s.trim().parse::<usize>().unwrap();
let mut arr: Vec<i64> = Vec::new();
for _i in 1..=n {
let mut s = String::new();
std::io::stdin().read_line(&mut s).unwrap();
let st = s.trim();
arr.push(st.parse::<i64>().unwrap());
}
let mut max_sub = -10000000000;
let mut min_value = arr0; for i in 1..n {
let sub = arri - min_value; if max_sub < sub { max_sub = sub}
if arri < min_value { min_value = arri }; }
println!("{}",max_sub);
}