2022-08-18:每一个序列都是[a,b]的形式，a ＜ b 序列连接的方式为，前一个序列的b，要等于后一个序列

fn main() {
    let mut arr: Vec<Vec<i32>> = vec![vec![1, 3], vec![3, 4], vec![4, 7]];
    let ans1 = max_len(&mut arr, 0, -1);
    println!("ans1 = {}", ans1);
    let ans1 = max_number_subsequence(&mut arr, 0, -1);
    println!("ans2 = {}", ans1);
}

fn max_len(arr: &mut Vec<Vec<i32>>, index: i32, pre_index: i32) -> i32 {
    if index == arr.len() as i32 {
        return 0;
    }
    // 还有序列可以选
    // index号序列
    // 不选
    let p1 = max_len(arr, index + 1, pre_index);
    // 选
    let mut p2 = 0;
    // [3,17] index(9,24)
    if pre_index == -1 || arr[pre_index as usize][1] == arr[index as usize][0] {
        // 才能选
        p2 = 1 + max_len(arr, index + 1, index);
    }
    return get_max(p1, p2);
}

// O(N^2)
fn max_number_subsequence(arr: &mut Vec<Vec<i32>>, index: i32, pre: i32) -> i32 {
    if index == arr.len() as i32 {
        return 0;
    }
    // 就是不要当前序列
    let p1 = max_number_subsequence(arr, index + 1, pre);
    // 要当前序列
    let mut p2 = -1;
    if pre == -1 || arr[pre as usize][1] == arr[index as usize][0] {
        p2 = 1 + max_number_subsequence(arr, index + 1, index);
    }
    return get_max(p1, p2);
}

fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}
Copy