Start learning free

LESSON 236 OF 414 · PARTIAL SUMS #1

Maximum Sum Subarray in Rust: Prefix Sums in O(n)

Practice O(n) Read the full explanation

( Prefix Sums Approach )


Given an input array that may contain both positive and negative integers, find the sum of continuous subarray of numbers which has the largest sum.

Example:

Input: nums = [-2, -5, 6, -2, -3, 1, 5, -6]
Output: 7
Explanation: sum([6, -2, -3, 1, 5]) = 7

Note:

Your algorithm should run in O(n) time and use at most O(n) extra space.


STEP 1 OF 7
    Ctrl + Enter to check

    RUST · PARTIAL SUMS #1

    Maximum Sum Subarray in Rust, explained

    Problem overview

    The function max_sum_subarray takes a vector of integers, positive or negative, and returns the largest sum of a non-empty continuous subarray. For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from [6, -2, -3, 1, 5].

    The statement allows O(n) time and up to O(n) extra space. This lesson reaches that bound with prefix sums, the running totals of the array.

    Approach: a subarray sum is a difference of two prefix sums

    The direct method tries every start and every end and adds the elements in between. Even with a running total that is O(n²) subarrays to look at, and it gets slow quickly as the vector grows. Prefix sums remove the inner work: once the total up to each position is known, any subarray sum is one subtraction, and the only remaining question is which start to subtract.

    Let partial_sum after element j be the total of everything from index 0 to j. The sum of the subarray from index i to j is then the prefix sum at j minus the prefix sum just before i. The array 6, -2, -3, 1, 5 starts after the prefix sum -7 and ends at the prefix sum 0, and 0 - (-7) = 7.

    So for a fixed end j, the best start is the one that subtracts the smallest earlier prefix sum. Scan left to right and keep two numbers: the running partial_sum and min_sum, the smallest prefix sum seen so far, including the empty prefix, which has sum 0. At each element the best subarray ending there has sum partial_sum - min_sum. The answer is the largest such value.

    The trace on the example:

    valpartial_summin_sum beforepartial_sum - min_sumresult
    -2-20-2-2
    -5-7-2-5-2
    6-1-766
    -2-3-746
    -3-6-716
    1-5-726
    50-777
    -6-6-717

    The order inside the loop matters. result is updated before min_sum, so the subtracted prefix always comes from strictly before the current element. That keeps the subarray non-empty. If min_sum were updated first, the current prefix could subtract itself and produce an empty subarray with sum 0.

    A second way to see the same algorithm is Kadane's algorithm, which tracks the best sum ending at each position directly and needs no stored prefix minimum. Both do one pass, and this version makes the connection to prefix sums explicit.

    Why is it enough to remember only the smallest earlier prefix sum? Any other start would subtract a larger number and leave a smaller total for the same end. So the best start for each end is the position where the prefix sum was lowest, and nothing else about the earlier elements needs to be kept.

    Step by step

    1. Declare partial_sum and min_sum as let mut i32 variables, both 0. The empty prefix has sum 0, and it is a legal place for a subarray to start.
    2. Declare result as nums[0]. The answer can be negative, so 0 is the wrong start. The first element is always a valid subarray sum.
    3. Loop over &nums with the variable val. Borrowing keeps the vector usable, and val is a &i32.
    4. Add the element to partial_sum. Rust lets += take the reference directly, so no dereference is needed.
    5. Update result with result.max(partial_sum - min_sum).
    6. Update min_sum with min_sum.min(partial_sum), so later elements can start after this position.
    7. Return result as the final expression.

    The solution in Rust

    impl Solution {
    fn max_sum_subarray(nums: Vec<i32>) -> i32 {
        let mut partial_sum: i32 = 0;
        let mut min_sum: i32 = 0;
        let mut result: i32 = nums[0];
        for val in &nums {
            partial_sum += val;
            result = result.max(partial_sum - min_sum);
            min_sum = min_sum.min(partial_sum);
        }
        result
    }
}

    The Rust details worth a closer look:

    • += with a reference. The standard library implements AddAssign<&i32> for i32, so partial_sum += val compiles where val is a &i32. A plain partial_sum = partial_sum + val also works, and writing *val is fine too.
    • max and min are methods. They come from the Ord trait and take the other value as an argument: result.max(x) is the larger of the two.
    • Nothing is stored. Despite the name "prefix sums", this version never builds a prefix array. Only the current total and the smallest one so far matter, so the memory use is constant.
    • Overflow. Under the lessons' optimized build, i32 arithmetic wraps silently, and a debug build would panic. Large inputs would call for i64.
    • Empty input. nums[0] panics on an empty vector.

    Complexity

    Time: O(n). One pass, with a constant amount of work for each element.

    Space: O(1). Three integers. The statement's allowance of O(n) would also cover storing the full prefix array, but it isn't needed.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1. With result starting at 0, the function would report 0, which no non-empty subarray has.
    • A single element. [-4] returns -4: partial_sum is -4, min_sum is still 0, and the difference is -4.
    • Updating min_sum too early. Moving that line above the result update lets an element subtract its own prefix and return an empty-subarray sum of 0 for all-negative input.
    • Starting min_sum too high. It must start at 0, not at nums[0] or i32::MAX. Otherwise subarrays that start at index 0 are never considered.

    Testing

    • [-2, -5, 6, -2, -3, 1, 5, -6] gives 7.
    • [-3, -1, -2] gives -1.
    • [-4] gives -4.
    Keep going with RustAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free