最长连续递增序列

  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. }