Start learning free

LESSON 235 OF 414 · PARTIAL SUMS #1

Maximum Sum Subarray in Rust: Kadane's Algorithm in O(n)

Practice O(n) Read the full explanation

( Kadane's Algorithm )


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 O(1) extra space.


STEP 1 OF 6
    Ctrl + Enter to check

    RUST · PARTIAL SUMS #1

    Maximum Sum Subarray in Rust, explained

    Problem overview

    The function max_sum_subarray receives a vector of integers that may be positive, negative or zero. It returns the largest sum that any non-empty continuous run of elements, a subarray, can have.

    For nums = [-2, -5, 6, -2, -3, 1, 5, -6] the answer is 7, from the subarray [6, -2, -3, 1, 5]. The statement requires O(n) time and O(1) extra space, so checking every subarray, which is O(n²) even with running sums, is too slow.

    Approach: the best subarray ending at each position

    Kadane's algorithm asks a smaller question at every position: what is the largest sum of a subarray that ends exactly here? Call it max_sum. The answer to the whole problem is the biggest max_sum seen at any position, because the best subarray has to end somewhere.

    The best subarray ending at the current element val has only two possible shapes. It is either val alone, or it is val attached to the best subarray ending at the previous position. Attaching helps only when that previous sum is positive. This gives the recurrence:

    max_sum = val + max(previous max_sum, 0)

    A negative running sum only drags the next element down, so it is dropped and the subarray restarts at val. A running sum of exactly 0 changes nothing either way.

    Here is the trace on the example:

    valmax_sumresult
    -2-2-2
    -5-5-2
    666
    -246
    -316
    126
    577
    -617

    At 6 the running sum restarts, because the sum before it, -5, was negative. After that it grows to 7 and the final -6 can't beat it.

    Step by step

    1. Create result from nums[0]. The answer can be negative, so starting at 0 would wrongly report 0 for an all-negative input. The first element is a real subarray sum, so it is a safe start.
    2. Create max_sum as 0. Before any element there is an empty prefix, with sum 0. The formula then makes the first max_sum equal to the first element.
    3. Loop over &nums. Borrowing the vector leaves it usable afterwards, and each val is a &i32.
    4. Apply the recurrence. Dereference with *val to get the number, and use max_sum.max(0) to choose between extending the previous subarray and restarting.
    5. Update result when max_sum is bigger.
    6. Return result as the last expression, with no semicolon.

    The solution in Rust

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

    The Rust details worth a closer look:

    • max is a method. a.max(b) returns the larger of two integers. It comes from the Ord trait, so max_sum.max(0) reads as "the larger of max_sum and 0". The 0 literal takes the type i32 from max_sum.
    • References in the loop. Iterating over &nums produces &i32 values. The expression *val + ... reads the integer behind the reference. Plain for val in nums would move the vector into the loop and consume it.
    • Tail expression. The last line, result, has no semicolon, so it is the function's return value. Adding a semicolon would make the function return () and the compiler would reject it.
    • Indexing an empty vector. nums[0] panics when the vector is empty. The lesson assumes at least one element.
    • Overflow. The lessons build with optimizations, where i32 arithmetic wraps silently. A debug build would panic instead. Sums beyond about 2.1 billion would need i64.

    Complexity

    Time: O(n). The loop touches each element once and does a constant amount of work for it.

    Space: O(1). Only two integers, result and max_sum, are kept, however long the vector is.

    Edge cases and common mistakes

    • All negative numbers. [-3, -1, -2] returns -1, the best single element. Starting result at 0 would give 0, an empty subarray that the problem doesn't allow.
    • A single element. [-4] returns -4.
    • A negative start. [-5, 4] returns 4. When 4 arrives, the running sum -5 is negative, so max_sum.max(0) is 0 and the subarray restarts at 4.
    • Returning max_sum. The last max_sum is the best sum ending at the final element, not the best overall. In the example it is 1, while the answer is 7.

    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