// LLP weighted interval scheduling: G[j] >= max(G[j-1], w[j] + G[p[j]]).

fn rhs(j: usize, g: &[i32], w: &[i32], p: &[usize]) -> i32 {
    let skip = g[j - 1];
    let take = w[j] + g[p[j]];
    skip.max(take)
}

fn llp_wis(w: &[i32], p: &[usize]) -> Vec<i32> {
    let n = w.len();
    let mut g = vec![0i32; n];
    let mut changed = true;
    while changed {
        changed = false;
        for j in 1..n {
            let v = rhs(j, &g, w, p);
            if g[j] < v { g[j] = v; changed = true; }
        }
    }
    g
}

fn main() {
    let w = [0, 4, 6, 5, 3, 7];
    let p = [0usize, 0, 0, 1, 3, 2];
    let g = llp_wis(&w, &p);
    println!("G = {:?}", g);
    println!("optimum = G[{}] = {}", g.len() - 1, g[g.len() - 1]);
}