2022-08-06：给定一个数组arr，长度为N，arr中所有的值都在1~K范围上， 你可以删除数字，目的是让arr的最长递增子序列长度小于K。 返回至少删除几个数字能达到目的。 N ＜= 10^4

use rand::Rng;
fn main() {
    let nn: i32 = 15;
    let kk: i32 = 6;
    let test_time: i32 = 10000;
    println!("测试开始");
    for _ in 0..test_time {
        let len = rand::thread_rng().gen_range(0, nn) + 1;
        let k = rand::thread_rng().gen_range(0, kk) + 1;
        let mut arr = random_array(len, k);
        let ans1 = min_remove1(&mut arr, k);
        let ans2 = min_remove2(&mut arr, k);
        if ans1 != ans2 {
            println!("ans1 = {:?}", ans1);
            println!("ans2 = {:?}", ans2);
            println!("出错了!");
            break;
        }
    }
    println!("测试结束");
}

// 暴力方法
// 为了验证
fn min_remove1(arr: &mut Vec, k: i32) -> i32 {
    let mut path0: Vec = vec![];
    for _ in 0..arr.len() {
        path0.push(0);
    }
    return process1(arr, 0, &mut path0, 0, k);
}

const MAX_VALUE: i32 = 2 , index: i32, path0: &mut Vec, size: i32, k: i32) -> i32 {
    if index == arr.len() as i32 {
        return if length_of_lis(path0, size) (a: T, b: T) -> T {
    if a (a: T, b: T) -> T {
    if a > b {
        a
    } else {
        b
    }
}

fn length_of_lis(arr: &mut Vec, size: i32) -> i32 {
    if size == 0 {
        return 0;
    }
    let mut ends: Vec = vec![];
    for _ in 0..size {
        ends.push(0);
    }
    ends[0] = arr[0];
    let mut right: i32 = 0;
    let mut l;
    let mut r;
    let mut m;
    let mut max = 1;
    for i in 1..size {
        l = 0;
        r = right;
        while l  ends[m as usize] {
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        right = get_max(right, l);
        ends[l as usize] = arr[i as usize];
        max = get_max(max, l + 1);
    }
    return max;
}

// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
fn zuo(arr: &mut Vec, index: i32, len: i32, k: i32) -> i32 {
    if len == k {
        return MAX_VALUE;
    }
    // 凑的(1...len)还不到(1...k)
    if index == arr.len() as i32 {
        return 0;
    }
    // 没凑到 = cur || len + 1 , k: i32) -> i32 {
    let n = arr.len() as i32;
    let mut dp: Vec> = vec![];
    for i in 0..n {
        dp.push(vec![]);
        for _ in 0..k {
            dp[i as usize].push(0);
        }
    }
    for i in 0..n {
        for j in 0..k {
            dp[i as usize][j as usize] = -1;
        }
    }
    return process2(arr, k, 0, 0, &mut dp);
}

fn process2(arr: &mut Vec, k: i32, index: i32, range: i32, dp: &mut Vec>) -> i32 {
    if range == k {
        return MAX_VALUE;
    }
    if index == arr.len() as i32 {
        return 0;
    }
    if dp[index as usize][range as usize] != -1 {
        return dp[index as usize][range as usize];
    }
    let mut ans: i32;
    if arr[index as usize] == range + 1 {
        let mut p1 = process2(arr, k, index + 1, range, dp);
        p1 += if p1 != MAX_VALUE { 1 } else { 0 };
        let p2 = process2(arr, k, index + 1, range + 1, dp);
        ans = get_min(p1, p2);
    } else {
        ans = process2(arr, k, index + 1, range, dp);
    }
    dp[index as usize][range as usize] = ans;
    return ans;
}

// 为了测试
fn random_array(len: i32, k: i32) -> Vec {
    let mut arr: Vec = vec![];
    for _ in 0..len {
        arr.push(rand::thread_rng().gen_range(0, k) + 1);
    }
    return arr;
}

// 暴力方法
// 为了验证
function minRemove1(arr: number[], k: number): number {
  return process1(arr, 0, new Array(arr.length), 0, k);
}

var MAX_VALUE: number = 2147483647;
function process1(
  arr: number[],
  index: number,
  path: number[],
  size: number,
  k: number
): number {
  if (index == arr.length) {
    return lengthOfLIS(path, size)  ends[m]) {
        l = m + 1;
      } else {
        r = m - 1;
      }
    }
    right = Math.max(right, l);
    ends[l] = arr[i];
    max = Math.max(max, l + 1);
  }
  return max;
}

// arr[0...index-1]上，选择了一些数字，之前的决定！
// len长度了！len = 3 ： 1 2 3
// arr[index....]是能够决定的，之前的，已经不能再决定了
// 返回：让最终保留的数字，凑不足k长度的情况下，至少要删几个！
function zuo(arr: number[], index: number, len: number, k: number): number {
  if (len == k) {
    return MAX_VALUE;
  }
  // 凑的(1...len)还不到(1...k)
  if (index == arr.length) {
    return 0;
  }
  // 没凑到 = cur || len + 1