1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104

//! # max_subarray_sum
//!
//! Finds maximum subarray sum in a list. This is also known
//! as max sum contigious subarray. If there are multiple such
//! subarrays, only the one that comes first is selected.
//!
//! The algorithm has time complexity of `O(N)` and space complexity
//! of `O(1)`.
//!
//! # Quick Start
//! ```
//! use max_subarray_sum::Elements;
//!
//! let list: Vec<i32> = vec![-2, -3, 4, -1, -2, 1, 5, -3];
//! 
//! //Or you can use an array instead:
//! let list: [i32; 8] = [-2, -3, 4, -1, -2, 1, 5, -3];
//!
//! let elements = Elements::new(&mut list);
//!
//! let max_sum: i32 = elements.find_max_sum().result();
//!
//! assert_eq!(7, max_sum);
//! ```

/// The `Elements` struct holds the list and related pieces of informations
/// of it.
pub struct Elements<'list> {
    list: &'list [i32],
    len: usize,
    max_sum: Option<i32>,
}

impl<'list> Elements<'list> {
    /// Returns a new instance of `Elements`.
    ///
    /// # Examples
    ///
    /// ```
    /// use max_subarray_sum::Elements;
    ///
    /// let mut list: Vec<i32> = vec![-2, -3, 4, -1, -2, 1, 5, -3];
    ///
    /// let len: usize = list.len();
    ///
    /// let mut elements = Elements::new(&mut list, len);
    /// ```
    pub fn new(list: &'list [i32]) -> Self {
        Elements {
            list,
            len: list.len(),
            max_sum: None,
        }
    }

    /// This method finds the max subarray sum. If there are multiple
    /// subarrays with equal sum it selects the subarray that came first.
    pub fn find_max_sum(&mut self) -> &Self {
        let list: &[i32] = self.list;

        let len: usize = self.len;

        let mut temp_sum: i32 = list[0];

        let mut max_sum: i32 = temp_sum;

        for i in 1..len {
            if temp_sum > 0 {
                temp_sum += list[i];
            } else {
                temp_sum = list[i];
            }

            if temp_sum > max_sum {
                max_sum = temp_sum;
            }
        }

        self.max_sum = Some(max_sum);

        self
    }

    /// This method returns the max subarray sum. We need to chain
    /// this method with `find_max_sum`.
    ///
    /// # Examples
    /// ```
    /// use max_subarray_sum::Elements;
    ///
    /// let mut list: Vec<i32> = vec![-2, -3, 4, -1, -2, 1, 5, -3];
    ///
    /// let len: usize = list.len();
    ///
    /// let mut elements = Elements::new(&mut list, len);
    ///
    /// let max_sum: i32 = elements.find_max_sum().result();
    ///
    /// assert_eq!(7, max_sum);
    /// ```
    pub fn result(&self) -> i32 {
        self.max_sum.unwrap()
    }
}