# Go4Fun - Functional programming and more # Rust Interview Puzzles: Maximum sum slice problem

### 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: ``
Explanation: The slice `` 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;
let mut best_start_index = 0;
let mut best_end_index = 0;

let mut current_sum = vec;
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