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