Jobs

Interviews

Discussions

Maximum Subarray

Medium

Rippling

0 views

Topics:

ArraysDynamic Programming

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Maximum Subarray

Medium

Rippling

0 views

Topics:

ArraysDynamic Programming

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1
Explanation: The subarray [1] has the largest sum 1.

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23
Explanation: The subarray [5,4,-1,7,8] has the largest sum 23.

Constraints:

1 <= nums.length <= 10⁵
-10⁴ <= nums[i] <= 10⁴

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array? Can I expect negative numbers, zeros, or only positive numbers?
What should I return if the input array is empty or null?
Is there a minimum size requirement for the subarray (must it contain at least one element), and if so, what should I return if the input array is empty?
Can you provide an example input array and the corresponding expected output to confirm my understanding?
Are there any constraints on the size of the input array 'nums'?

Brute Force Solution

Approach

The brute force strategy for finding the largest sum from a group of numbers involves checking every possible consecutive grouping of numbers. It's like trying out all possible slices of a loaf of bread to see which slice is the heaviest. We check each possible slice and keep track of the largest slice sum we've encountered so far.

Here's how the algorithm would work step-by-step:

First, calculate the sum of the first number by itself.
Next, calculate the sum of the first two numbers.
Continue adding one more number at a time, calculating the sum for each lengthening group that starts from the beginning.
Then, start again, but this time begin with the second number. Calculate the sum of the second number by itself.
Continue adding one more number at a time, calculating the sum for each lengthening group that starts from the second number.
Repeat this process, each time starting at the next number in the group. Continue until you've started at every number.
Keep track of the largest sum you find during all of these calculations.
After checking all possible consecutive number groups, the largest sum you tracked is the answer.

Code Implementation

def maximum_subarray_brute_force(numbers):
    maximum_sum_so_far = float('-inf')

    # Iterate through all possible start indices.
    for start_index in range(len(numbers)):

        current_sum = 0

        # Iterate through all possible end indices starting from start_index.
        for end_index in range(start_index, len(numbers)):
            current_sum += numbers[end_index]

            # Update maximum_sum_so_far if current_sum is greater.
            maximum_sum_so_far = max(maximum_sum_so_far, current_sum)

    return maximum_sum_so_far

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through the array using nested loops. The outer loop iterates 'n' times, where 'n' is the number of elements in the array, defining the starting position of the subarray. The inner loop, for each starting position, iterates through the remaining elements to calculate the sum of all possible subarrays starting at that position. This results in roughly n * (n+1) / 2 calculations. Therefore, the time complexity is O(n²).

Space Complexity

O(1) – The provided brute force algorithm calculates sums iteratively without using any auxiliary data structures that scale with the input size. It only maintains a variable to store the current sum and another variable to store the maximum sum found so far. Since the extra space used does not depend on the input array's length (N), the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the maximum sum of a continuous set of numbers involves tracking the current best sum as we go. If the current set of numbers starts hurting the sum, we simply start a new set.

Here's how the algorithm would work step-by-step:

Start with the first number in the set and consider it as our initial best sum.
Move to the next number. Check: Does adding this number to our current set of numbers make the sum better or worse?
If adding the number makes the sum worse, it's better to start a new set of numbers from this point. Forget the previous numbers.
If adding the number makes the sum better, include it in our current set. Continue this process.
At each step, compare the current sum of the set to our best sum seen so far. If the current sum is better, update the best sum.
Continue until we've gone through all the numbers. The best sum we've recorded is the answer.

Code Implementation

def max_subarray(numbers):
    current_max = numbers[0]
    overall_max = numbers[0]

    for i in range(1, len(numbers)):
        # Decide if extending the subarray helps.
        current_max = max(numbers[i], current_max + numbers[i])

        # Update overall max sum if needed
        overall_max = max(overall_max, current_max)

    return overall_max

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the input array nums exactly once. In each iteration, it performs a constant number of operations: adding the current number to the current sum, comparing the current sum with the maximum sum seen so far, and potentially resetting the current sum to the current number. Therefore, the time complexity is directly proportional to the number of elements (n) in the array, resulting in a linear time complexity of O(n).

Space Complexity

O(1) – The algorithm described only uses a couple of variables to store the current sum and the best sum so far. These variables require a constant amount of memory regardless of the size of the input array, which we can denote as N. No additional data structures that scale with the input size are utilized. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException as there are no subarrays to sum.
Array with a single element	Return the value of that single element as it's the maximum possible subarray sum.
Array with all negative numbers	Return the largest negative number in the array, as that's the best possible contiguous sum.
Array with all zeros	Return 0, as the contiguous subarray [0] is the maximum possible sum.
Array with large positive and negative numbers (potential integer overflow)	Use a data type that can accommodate larger sums, like long in Java or Python.
Array with highly skewed positive and negative numbers, concentrated in specific regions	Kadane's algorithm efficiently handles this case by continuously updating the maximum sum.
Maximum subarray spanning almost the entire array with a small negative element interrupting it	Kadane's algorithm will correctly identify and consider or disregard the interruption to maximize the sum.
Very large array size (performance consideration)	Kadane's algorithm has O(n) time complexity and constant space complexity, making it suitable for large arrays.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers within the input array? Can I expect negative numbers, zeros, or only positive numbers?
What should I return if the input array is empty or null?
Is there a minimum size requirement for the subarray (must it contain at least one element), and if so, what should I return if the input array is empty?
Can you provide an example input array and the corresponding expected output to confirm my understanding?
Are there any constraints on the size of the input array 'nums'?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, calculate the sum of the first number by itself.
Next, calculate the sum of the first two numbers.
Continue adding one more number at a time, calculating the sum for each lengthening group that starts from the beginning.
Then, start again, but this time begin with the second number. Calculate the sum of the second number by itself.
Continue adding one more number at a time, calculating the sum for each lengthening group that starts from the second number.
Repeat this process, each time starting at the next number in the group. Continue until you've started at every number.
Keep track of the largest sum you find during all of these calculations.
After checking all possible consecutive number groups, the largest sum you tracked is the answer.

Code Implementation

def maximum_subarray_brute_force(numbers):
    maximum_sum_so_far = float('-inf')

    # Iterate through all possible start indices.
    for start_index in range(len(numbers)):

        current_sum = 0

        # Iterate through all possible end indices starting from start_index.
        for end_index in range(start_index, len(numbers)):
            current_sum += numbers[end_index]

            # Update maximum_sum_so_far if current_sum is greater.
            maximum_sum_so_far = max(maximum_sum_so_far, current_sum)

    return maximum_sum_so_far

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Start with the first number in the set and consider it as our initial best sum.
Move to the next number. Check: Does adding this number to our current set of numbers make the sum better or worse?
If adding the number makes the sum worse, it's better to start a new set of numbers from this point. Forget the previous numbers.
If adding the number makes the sum better, include it in our current set. Continue this process.
At each step, compare the current sum of the set to our best sum seen so far. If the current sum is better, update the best sum.
Continue until we've gone through all the numbers. The best sum we've recorded is the answer.

Code Implementation

def max_subarray(numbers):
    current_max = numbers[0]
    overall_max = numbers[0]

    for i in range(1, len(numbers)):
        # Decide if extending the subarray helps.
        current_max = max(numbers[i], current_max + numbers[i])

        # Update overall max sum if needed
        overall_max = max(overall_max, current_max)

    return overall_max

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input array	Return 0 or throw an IllegalArgumentException as there are no subarrays to sum.
Array with a single element	Return the value of that single element as it's the maximum possible subarray sum.
Array with all negative numbers	Return the largest negative number in the array, as that's the best possible contiguous sum.
Array with all zeros	Return 0, as the contiguous subarray [0] is the maximum possible sum.
Array with large positive and negative numbers (potential integer overflow)	Use a data type that can accommodate larger sums, like long in Java or Python.
Array with highly skewed positive and negative numbers, concentrated in specific regions	Kadane's algorithm efficiently handles this case by continuously updating the maximum sum.
Maximum subarray spanning almost the entire array with a small negative element interrupting it	Kadane's algorithm will correctly identify and consider or disregard the interruption to maximize the sum.
Very large array size (performance consideration)	Kadane's algorithm has O(n) time complexity and constant space complexity, making it suitable for large arrays.