// LLP-LIS: G[j] >= G[i] + 1 for every i in pre(j) (i < j with A[i] < A[j]).

fn llp_lis(a: &[i32]) -> Vec<i32> {
    let n = a.len();
    let mut pre: Vec<Vec<usize>> = vec![vec![]; n];
    for j in 0..n {
        for i in 0..j {
            if a[i] < a[j] { pre[j].push(i); }
        }
    }
    let mut g = vec![1i32; n];
    let mut changed = true;
    while changed {
        changed = false;
        for j in 0..n {
            let mut best = g[j];
            for &i in &pre[j] {
                if g[i] + 1 > best { best = g[i] + 1; }
            }
            if best > g[j] { g[j] = best; changed = true; }
        }
    }
    g
}

fn main() {
    let a = [3, 10, 2, 1, 20, 4];
    let g = llp_lis(&a);
    let lis = *g.iter().max().unwrap_or(&0);
    println!("G = {:?}, LIS length = {}", g, lis);
}