Problem statement

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.
Link to problem

Example 1

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6

Example 2

Input: nums = [1]
Output: 1

Example 3

Input: nums = [5,4,-1,7,8]
Output: 23

Solutions

Approach 1: Cubic

The first approach anyone would think of, finding the sum of ALL sub arrays.
Unfortunately, the first implementation that I could think of was of a cubic time complexity.

You essentially pick an element from the array, and find the sum of every element from there.
e.g., if [1,2,3,4] was your array you would calculate them like so

[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[2]
[2, 3]
[2, 3, 4]
...

Pseudocode

start loop from i=0 to n-1
    start loop from j=i to n-1
        initialize a sum variable to 0
        start loop from i to j(inclusive)
            sum += numbers[k]
        if sum is more than max_sum
            sum is the new max_sum

Implementation in Rust

fn max_sub_array(numbers: Vec<i32>) -> i32 {
    let mut max_sum = -9999;
    for i in 0..numbers.len() {
        for j in i..numbers.len() {
            let mut sum = 0;
            for k in i..j+1 {
                sum += numbers[k];
            }
            if sum > max_sum {
                max_sum = sum;
            }
        }
    }
    max_sum
}

Time Complexity: $O(n^3)$
Runtime on LeetCode: Time Limit Exceeded

Approach 2: Quadratic

Very similar to the first approach, we just get rid of the k loop and replace it with a variable instead.
Still not as efficient but far better than the first approach as it has time complexity of $O(n^2)$.

The idea behind this is that when we pick a subarray, in order to get the next subarray, we are adding one element that comes after the subarray.

Implementation in Rust

fn max_sub_array(numbers: Vec<i32>) -> i32 {
    let mut max_sum = -9999;
        for i in 0..numbers.len() {
            let mut sum = 0;
            for j in i..numbers.len() {
                sum += numbers[j];
                if sum > max_sum {
                    max_sum = sum;
                }
            }
        }
    max_sum
}

Time Complexity: $O(n^2)$
Runtime on LeetCode: Time Limit Exceeded

Approach 3: Kadane’s Algorithm

The main idea behind Kadane’s Algorithm is that if you are at nth index, then the max subarray ending at nth index is either element at nth index or element at nth index along with the one prior to it.

Pseudocode

set max_current and max_sum to numbers[0]
begin loop from 1 to n - 1
    max_current = max(numbers[i], numbers[i] + max_current)
    max_sum = max(max_current, max_sum)
return max_sum

Implementation in Rust

fn max_sub_array(numbers:Vec<i32>) -> i32 {
    let mut max_sum = numbers[0];
    let mut max_current = numbers[0];

    for i in 1..numbers.len() {
        max_current = std::cmp::max(numbers[i], max_current + numbers[i]);
        max_sum = std::cmp::max(max_sum, max_current);
    }
    max_sum
}

Time Complexity: $O(n)$
Runtime on LeetCode: $13$ms

Resources

Note: I’ve spent about 2 hours straight on this problem and have not covered various other approaches that include other dynamic programming concepts as well as an approach that utilizes divide and conquer concept.

A lot of my time went into researching during this question because I was pretty lost after coming up with just one working approach, which was the first one and the worst one.

I am saving a few resources here in case I decide to tackle this problem again in future with a different approach.
Feel free to make a contribution here if you want to cover other approaches :)

Here are the resources I used:

  1. CS Dojo’s Kadane Algorithm Explanation
  2. More approaches
  3. This problem on EnjoyAlgorithms, wasn’t that good but few tidbits from there can be very insightful.
  4. NeetCode’s video on this problem