Problem

In a provided vector vec we need to find a slice with the largest sum of the elements. This problem is commonly referred to as Maximum subarray problem.

Example 1:

Input: vec = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: [4, -1, 2, 1]
Explanation: The slice [4, -1, 2, 1] has the largest sum of elements (6).

Example 2:

Input: vec = [-4, 1, 2, 3, -5]
Output: [1, 2, 3]
Explanation: The slice [1, 2, 3] has the largest sum of elements (6).

Example 3:

Input: vec = [-4, 1, -5]
Output: [1]
Explanation: The slice [1] has the largest sum of elements (1).

Example 4:

Input: vec = [-4, -3, -5]
Output: [-3]
Explanation: The slice [-3] has the largest sum of elements (-3).

Solution

fn find_max_sum_slice(vec: &Vec<i32>) -> &[i32] {
    if vec.is_empty() {
        return &[];
    }

    let mut best_sum = vec[0];
    let mut best_start_index = 0;
    let mut best_end_index = 0;

    let mut current_sum = vec[0];
    let mut current_start_index = 0;

    (1..vec.len()).for_each(|i| {
        if current_sum <= 0 {
            //if the current sum is <= 0, we start tracking a new sequence from the current element
            current_start_index = i;
            current_sum = vec[i];
        } else {
            //otherwise we continue the currently tracked sequence
            current_sum += vec[i];
        }
        //then we update the best sum if the current sum is greater
        if current_sum >= best_sum {
            best_sum = current_sum;
            best_start_index = current_start_index;
            best_end_index = i;
        }
    });

    &vec[best_start_index..best_end_index + 1]
}

Explanation

The solution for this problem uses Kadane's algorithm. We iterate over the vector vec searching for a sequence of elements that could potentially become the sequence with the largest sum. If current_sum <= 0 then we "reset" the currently tracked sequence and start tracking a new sequence starting from the current index (update current_start_index to the current index i and current_sum to the current element vec[i]), because having a negative current_sum doesn't help the currently tracked sequence to become the largest anyway. But if current_sum is positive then we continue tracking the current sequence (we don't update current_start_index, but we add the current element vec[i] to current_sum). Then during the same iteration we check if current_sum >= best_sum and update best_sum we have found so far and its indices (best_start_index, best_end_index).

Complexity

The time complexity of this solution is O(n) (n is a size of the input vector). The auxiliary space complexity is constant (O(1)).

---

Rust Playground with this code