最大子数组

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