最大子数组

  1. /// ## maximum subarray via Dynamic Programming
  3. /// maximum_subarray(array) find the subarray (containing at least one number) which has the largest sum
  4. /// and return its sum.
  5. ///
  6. /// A subarray is a contiguous part of an array.
  7. ///
  8. /// Arguments:
  9. ///     * `array` - an integer array
  10. /// Complexity
  11. ///     - time complexity: O(array.length),
  12. ///     - space complexity: O(array.length),
  13. pub fn maximum_subarray(array: &[i32]) -> i32 {
  14.     let mut dp = vec![0; array.len()];
  15.     dp[0] = array[0];
  16.     let mut result = dp[0];
  18.     for i in 1..array.len() {
  19.         if dp[i - 1] > 0 {
  20.             dp[i] = dp[i - 1] + array[i];
  21.         } else {
  22.             dp[i] = array[i];
  23.         }
  24.         result = result.max(dp[i]);
  25.     }
  27.     result
  28. }
  30. #[cfg(test)]
  31. mod tests {
  32.     use super::*;
  34.     #[test]
  35.     fn non_negative() {
  36.         //the maximum value: 1 + 0 + 5 + 8 = 14
  37.         let array = vec![1, 0, 5, 8];
  38.         assert_eq!(maximum_subarray(&array), 14);
  39.     }
  41.     #[test]
  42.     fn negative() {
  43.         //the maximum value: -1
  44.         let array = vec![-3, -1, -8, -2];
  45.         assert_eq!(maximum_subarray(&array), -1);
  46.     }
  48.     #[test]
  49.     fn normal() {
  50.         //the maximum value: 3 + (-2) + 5 = 6
  51.         let array = vec![-4, 3, -2, 5, -8];
  52.         assert_eq!(maximum_subarray(&array), 6);
  53.     }
  55.     #[test]
  56.     fn single_element() {
  57.         let array = vec![6];
  58.         assert_eq!(maximum_subarray(&array), 6);
  59.         let array = vec![-6];
  60.         assert_eq!(maximum_subarray(&array), -6);
  61.     }
  62. }