solve_leetcode/problems/
0300-longest-increasing-subsequence.rs

1/// f(i) represents the length of LIS of nums[0..=i] which ends with nums[i]
2///
3/// Then we want max(f(0), f(1), ..., f(n-1))
4///
5/// f(i) = max(
6///     if nums[i] > nums[0] { f(0) + 1 } else { 1 },
7///     ...
8///     if nums[i] > nums[i-1] { f(i-1) + 1 } else { 1 },
9/// )
10///
11/// f(0) = 1
12pub mod dp {
13    pub fn solve(nums: &[i32]) -> usize {
14        let n = nums.len();
15        let mut res = vec![1; n];
16
17        for i in 1..n {
18            res[i] = (0..i)
19                .map(|j| if nums[i] > nums[j] { res[j] + 1 } else { 1 })
20                .max()
21                .unwrap();
22        }
23
24        res.into_iter().max().unwrap()
25    }
26}
27
28// pub mod binary_search {
29//     pub fn solve(nums: &[i32]) -> usize {
30//         todo!()
31//     }
32// }
33
34#[cfg(test)]
35mod tests {
36    #[test]
37    fn problem_0300() {
38        for solve in [
39            //
40            super::dp::solve,
41        ] {
42            for (piles, result) in [
43                //
44                (&[1][..], 1),
45                (&[10, 9, 2, 5, 3, 7, 101, 18], 4),
46                (&[0, 1, 0, 3, 2, 3], 4),
47                (&[7, 7, 7, 7, 7, 7, 7], 1),
48            ] {
49                let solved = solve(piles);
50
51                assert_eq!(solved, result);
52            }
53        }
54    }
55}