最长连续递增序列

1. pub fn longest_continuous_increasing_subsequence<T: Ord>(input_array: &[T]) -> &[T] {
2. let length: usize = input_array.len();

4. //Handle the base cases
5. if length <= 1 {
6. return input_array;
7. }

9. //Create the array to store the longest subsequence at each location
10. let mut tracking_vec = vec![1; length];

12. //Iterate through the input and store longest subsequences at each location in the vector
13. for i in (0..length - 1).rev() {
14. if input_array[i] < input_array[i + 1] {
15. tracking_vec[i] = tracking_vec[i + 1] + 1;
16. }
17. }

19. //Find the longest subsequence
20. let mut max_index: usize = 0;
21. let mut max_value: i32 = 0;
22. for (index, value) in tracking_vec.iter().enumerate() {
23. if value > &max_value {
24. max_value = *value;
25. max_index = index;
26. }
27. }

29. &input_array[max_index..max_index + max_value as usize]
30. }

32. #[cfg(test)]
33. mod tests {
34. use super::longest_continuous_increasing_subsequence;

36. #[test]
37. fn test_longest_increasing_subsequence() {
38. //Base Cases
39. let base_case_array: [i32; 0] = [];
40. assert_eq!(
41. &longest_continuous_increasing_subsequence(&base_case_array),
42. &[]
43. );
44. assert_eq!(&longest_continuous_increasing_subsequence(&[1]), &[1]);

46. //Normal i32 Cases
47. assert_eq!(
48. &longest_continuous_increasing_subsequence(&[1, 2, 3, 4]),
49. &[1, 2, 3, 4]
50. );
51. assert_eq!(
52. &longest_continuous_increasing_subsequence(&[1, 2, 2, 3, 4, 2]),
53. &[2, 3, 4]
54. );
55. assert_eq!(
56. &longest_continuous_increasing_subsequence(&[5, 4, 3, 2, 1]),
57. &[5]
58. );
59. assert_eq!(
60. &longest_continuous_increasing_subsequence(&[5, 4, 3, 4, 2, 1]),
61. &[3, 4]
62. );

64. //Non-Numeric case
65. assert_eq!(
66. &longest_continuous_increasing_subsequence(&['a', 'b', 'c']),
67. &['a', 'b', 'c']
68. );
69. assert_eq!(
70. &longest_continuous_increasing_subsequence(&['d', 'c', 'd']),
71. &['c', 'd']
72. );
73. }
74. }