53. Maximum Subarray

MediumArrayDivide and ConquerDynamic Programming
Leetcode Link

Problem Description

The problem gives us an array of integers called nums. Our task is to find a contiguous subarray within this array that adds up to the maximum sum possible and then return this maximum sum. The term "subarray" here refers to a sequence of consecutive elements from the original array. It's important to note that the array may contain both positive and negative numbers, and the subarray with the largest sum must contain at least one element.

Intuition

To solve this problem, we use a well-known algorithm called Kadane's algorithm. The intuition behind this approach is to iterate through each element in the array while keeping track of two important variables: f and ans. Here, f tracks the maximum sum of the subarray ending at the current position, and ans keeps the overall maximum sum found so far.

At each step of the iteration, we decide whether to "start fresh" with the current element (if the sum up to this point is negative, since it would only reduce the sum of the subarray) or to add it to the current running sum f. We do this by comparing f with 0 (essentially dropping the subarray if f is negative) and then add the current element to f.

Then, we update ans to be the maximum of ans or the new sum f. By the end of the iteration, we would have examined every subarray and ans holds the value of the largest subarray sum.

The key idea is to keep adding elements to the current sum if it contributes positively and start a new subarray sum whenever the running sum becomes negative.

Learn more about Divide and Conquer and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Depth first search is equivalent to which of the tree traversal order?

Solution Approach

The implementation of the solution is straightforward once the intuition behind the problem is clear. The solution uses no additional data structures other than simple variables for tracking the current sum and the maximum sum.

The algorithm initializes ans and f with the first element of the array. It assumes that the best subarray could at least be the first element itself. Then it begins to iterate from the second element of the array all the way to the last element.

For each element x in the array:

  1. We update f to be the maximum of f + x or 0 + x. The reason we compare with 0 is to decide whether to start a new subarray from the current element (in case the previous f was negative and thus, doesn't help in increasing the sum).

    This is implemented as:

    1f = max(f, 0) + x

  2. We update ans to be the maximum of ans or the new f. This way, we ensure ans always holds the maximum sum found so far.

    This is implemented as:

    1ans = max(ans, f)

  3. After the loop terminates, ans will hold the maximum subarray sum that we are looking for, which gets returned as the result.

This approach only requires O(1) extra space for the tracking variables and O(n) time complexity, as it passes through the array only once. It's a prime example of an efficient algorithm that combines simple ideas to solve a problem that might seem complex at first glance.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Example Walkthrough

Let's walk through an example to illustrate the solution approach. Consider the following array of integers:

1nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

We want to find a contiguous subarray that has the maximum sum. According to Kadane's algorithm, we initialize our tracking variables:

1f = nums[0] = -2
2ans = nums[0] = -2

Now, let's iterate through the array starting from the second element.

  1. At index 1, nums[1] = 1

    • We calculate f = max(f + nums[1], nums[1]) = max(-2 + 1, 1) = 1
    • We then update ans = max(ans, f) = max(-2, 1) = 1

  2. At index 2, nums[2] = -3

    • Update f = max(f + nums[2], nums[2]) = max(1 + (-3), -3) = max(-2, -3) = -2
    • Since f is less than ans, we don't update ans. ans remains 1.

  3. At index 3, nums[3] = 4

    • Update f = max(f + nums[3], nums[3]) = max(-2 + 4, 4) = 4
    • Update ans = max(ans, f) = max(1, 4) = 4

  4. At index 4, nums[4] = -1

    • Update f = max(f + nums[4], nums[4]) = max(4 + (-1), -1) = 3
    • ans remains the same as f is less than ans.

  5. At index 5, nums[5] = 2

    • Update f = max(f + nums[5], nums[5]) = max(3 + 2, 2) = 5
    • Update ans = max(ans, f) = max(4, 5) = 5

  6. At index 6, nums[6] = 1

    • Update f = max(f + nums[6], nums[6]) = max(5 + 1, 1) = 6
    • Update ans = max(ans, f) = max(5, 6) = 6

  7. At index 7, nums[7] = -5

    • Update f = max(f + nums[7], nums[7]) = max(6 + (-5), -5) = 1
    • ans remains 6.

  8. Finally, at index 8, nums[8] = 4

    • Update f = max(f + nums[8], nums[8]) = max(1 + 4, 4) = 5
    • Update ans = max(ans, f) = max(6, 5) = 6

After iterating through all elements, we find that the maximum sum of a contiguous subarray in nums is 6, and the contiguous subarray that gives this sum is [4, -1, 2, 1]. Thus our function would return 6 as the final result.

Solution Implementation

1from typing import List
2
3class Solution:
4    def maxSubArray(self, nums: List[int]) -> int:
5        # Initialize the maximum subarray sum with the first element.
6        max_sum = current_sum = nums[0]
7      
8        # Iterate through the remaining elements in the list starting from the second element.
9        for num in nums[1:]:
10            # Update the current subarray sum. Add the current number to the current sum,
11            # or reset it to the current number if the current sum is negative.
12            current_sum = max(current_sum + num, num)
13          
14            # Update the maximum subarray sum if the current subarray sum is greater.
15            max_sum = max(max_sum, current_sum)
16      
17        # Return the maximum subarray sum found.
18        return max_sum
19
1class Solution {
2    public int maxSubArray(int[] nums) {
3        // `maxSoFar` holds the maximum subarray sum found so far
4        int maxSoFar = nums[0];
5        // `currentMax` holds the maximum sum of the subarray ending at the current position
6        int currentMax = nums[0];
7      
8        // Loop through the array starting from the second element
9        for (int i = 1; i < nums.length; ++i) {
10            // Update `currentMax` to be the maximum of `currentMax` + current element or 0 + current element
11            // This is the essence of the Kadane's algorithm which decides whether to start a new subarray or continue with the current one
12            currentMax = Math.max(currentMax, 0) + nums[i];
13          
14            // If the current computed `currentMax` is greater than `maxSoFar`, update `maxSoFar`
15            maxSoFar = Math.max(maxSoFar, currentMax);
16        }
17        // Return the largest sum
18        return maxSoFar;
19    }
20}
21
1#include <vector>
2#include <algorithm> // for std::max
3
4class Solution {
5public:
6    int maxSubArray(vector<int>& nums) {
7        // Initialize current max to the first element of the vector
8        int currentMax = nums[0];
9        // Initialize global max with the same value
10        int globalMax = nums[0];
11      
12        // Loop through the elements starting from the second element
13        for (int i = 1; i < nums.size(); ++i) {
14            // Update current max; if it becomes negative, reset it to zero
15            currentMax = std::max(currentMax, 0) + nums[i];
16            // Update global max with the maximum value between current and global max
17            globalMax = std::max(globalMax, currentMax);
18        }
19      
20        // Final answer which is the maximum subarray sum
21        return globalMax;
22    }
23};
24
1/**
2 * Finds the contiguous subarray within an array (containing at least one number)
3 * which has the largest sum and returns that sum.
4 * @param nums The array of numbers.
5 * @return The maximum subarray sum.
6 */
7function maxSubArray(nums: number[]): number {
8    // Initialize the answer and the running sum with the first element of the array.
9    let maxSum = nums[0];
10    let currentSum = nums[0];
11
12    // Iterate over the array starting from the second element.
13    for (let i = 1; i < nums.length; ++i) {
14        // Update the current sum to be the maximum between the current sum with zero (to discard negative sums)
15        // and then add the current element to include it in the subarray.
16        currentSum = Math.max(currentSum, 0) + nums[i];
17
18        // Update the maximum sum if the current sum is greater.
19        maxSum = Math.max(maxSum, currentSum);
20    }
21
22    // Return the final maximum sum found.
23    return maxSum;
24}
25
Not Sure What to Study? Take the 2-min Quiz

Which type of traversal does breadth first search do?

Time and Space Complexity

Time Complexity

The given code snippet consists of a single loop that iterates through the list nums. The loop starts from the second element and goes till the last element, performing constant time operations in each iteration. The max function is also O(1). Therefore, the time complexity is O(n), where n is the number of elements in the input list nums.

Space Complexity

The space complexity of the algorithm is O(1). It only uses a fixed amount of extra space: two integer variables ans and f to store the maximum sum and the current sum, respectively. These do not depend on the size of the input list, thus the algorithm uses constant extra space.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following array represent a max heap?

Recommended Readings

Divide and Conquer Intro

https algomonster s3 us east 2 amazonaws com cover_photos dnd svg Divide and Conquer The main idea of divide and conquer is to split the main problem into two smaller components assuming that each one of the components had already been solved recursively and then try to solve the bigger

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«