use rand::Rng;
fn main() {
    let nn = 100;
    let vv = 1000;
    let test_time = 2000;
    println!("测试开始");
    for _ in 0..test_time {
        let n = rand::thread_rng().gen_range(0, nn) + 1;
        let mut arr = random_array(n, vv);
        let ans1 = max_animals1(&mut arr);
        let ans2 = max_animals2(&mut arr);
        if ans1 != ans2 {
            println!("出错了");
            println!("{:?}", arr);
            println!("");
            println!("ans1 = {}", ans1);
            println!("ans2 = {}", ans2);
            break;
        }
    }
    println!("测试结束");
}

// 普通动态规划
// 非常一般的方法
// 来自背包的思路
fn max_animals1(arr: &mut Vec<i32>) -> i32 {
    let mut sum = 0;
    for num in arr.iter() {
        sum += *num;
    }
    let mut dp: Vec<Vec<i32>> = vec![];
    for i in 0..arr.len() as i32 {
        dp.push(vec![]);
        for _ in 0..sum + 1 {
            dp[i as usize].push(0);
        }
    }
    for i in 0..arr.len() as i32 {
        for j in 0..=sum {
            dp[i as usize][j as usize] = -1;
        }
    }
    return process1(arr, 0, 0, &mut dp);
}

fn process1(arr: &mut Vec<i32>, index: i32, pre: i32, dp: &mut Vec<Vec<i32>>) -> i32 {
    if index == arr.len() as i32 {
        return 0;
    }
    if dp[index as usize][pre as usize] != -1 {
        return dp[index as usize][pre as usize];
    }
    let p1 = process1(arr, index + 1, pre, dp);
    let mut p2 = 0;
    if arr[index as usize] >= pre {
        p2 = 1 + process1(arr, index + 1, pre + arr[index as usize], dp);
    }
    let ans = get_max(p1, p2);
    dp[index as usize][pre as usize] = ans;
    return ans;
}

// 最优解
// 如果arr长度为N，时间复杂度O(N*logN)
fn max_animals2(arr: &mut Vec<i32>) -> i32 {
    if arr.len() == 0 {
        return 0;
    }
    // ends数组
    let mut ends: Vec<i32> = vec![];
    for _ in 0..arr.len() + 1 {
        ends.push(0);
    }
    ends[0] = 0;
    let mut ends_size = 1;
    let mut max: i32 = 1;
    for i in 0..arr.len() as i32 {
        let mut l: i32 = 0;
        let mut r: i32 = ends_size - 1;
        let mut m: i32;
        let mut find: i32 = 0;
        while l <= r {
            m = (l + r) / 2;
            if ends[m as usize] <= arr[i as usize] {
                find = m;
                l = m + 1;
            } else {
                r = m - 1;
            }
        }
        if find == ends_size - 1 {
            ends[ends_size as usize] = ends[(ends_size - 1) as usize] + arr[i as usize];
            ends_size += 1;
        } else {
            if ends[(find + 1) as usize] > ends[find as usize] + arr[i as usize] {
                ends[(find + 1) as usize] = ends[find as usize] + arr[i as usize];
            }
        }
        max = get_max(max, find + 1);
    }
    return max;
}

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

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