lis

gistfile1.txt

use std::cmp;

fn lis(datas: &Vec<(isize, isize)>) -> isize {
    let datas: Vec<(isize, isize)> = datas.iter().map(|&x| {
        if x.0 > x.1 {
            (x.1, x.0)
        } else {
            (x.0, x.1)
        }
    }).collect();

    let mut map = vec![];
    for _ in 0..datas.len() { map.push(0); }

    for i in 0..datas.len() {
        let mut max_num = 0;
        for j in 0..i {
            let (a1, b1) = datas[j];
            let (a2, b2) = datas[i];

            let max_1 = cmp::max(a1, b1);
            let min_2 = cmp::min(a2, b2);

            if max_1 <= min_2 {
                max_num = map[j];
            }
        }
        map[i] = max_num + 1;
    }

    *map.iter().max().unwrap()
}

fn main() {
    assert_eq!(1, lis(&vec![(1, 2), (2, 1)]));
    assert_eq!(2, lis(&vec![(1, 2), (2, 4), (3, 1), (4, 3)]));
    assert_eq!(3, lis(&vec![(1, 5), (1, 3), (4, 2), (7, 6), (9, 8)]));
    assert_eq!(4, lis(&vec![(1, 5), (1, 2), (2, 3), (4, 3), (5, 6)]));
}