### 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)`

).