TIC
The Interns Company

Maximum Subarray

EasyAcceptance: 49.7%
ArrayDivide and ConquerDynamic Programming

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.

Constraints:

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Input Format:

  • An array of integers nums

Output Format:

  • The sum of the contiguous subarray with the largest sum

Examples:

Example 1:

Input:

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

Output:

6

Explanation:

The contiguous subarray [4,-1,2,1] has the largest sum = 6.

Example 2:

Input:

nums = [1]

Output:

1

Explanation:

The array only has one element, so the maximum subarray is just that element.

Example 3:

Input:

nums = [5,4,-1,7,8]

Output:

23

Explanation:

The contiguous subarray [5,4,-1,7,8] has the largest sum = 23.

Solutions

Kadane's Algorithm

Time: O(n)
Space: O(1)

Maintain a running sum and reset it when it becomes negative.

Dynamic Programming Approach

Time: O(n)
Space: O(n)

Define DP[i] as the maximum subarray sum ending at index i.

Divide and Conquer Approach

Time: O(n log n)
Space: O(log n) for the recursion stack

Divide the array into two halves and find the maximum subarray sum in the left half, right half, and crossing the middle.

Algorithm Walkthrough

Example input: nums = [-2,1,-3,4,-1,2,1,-5,4]

Step-by-step execution:

  1. maxSum = -2, currentSum = -2
  2. i=1, nums[1]=1: currentSum = max(1, -2+1) = 1, maxSum = max(-2, 1) = 1
  3. i=2, nums[2]=-3: currentSum = max(-3, 1-3) = -2, maxSum = max(1, -2) = 1
  4. i=3, nums[3]=4: currentSum = max(4, -2+4) = 4, maxSum = max(1, 4) = 4
  5. i=4, nums[4]=-1: currentSum = max(-1, 4-1) = 3, maxSum = max(4, 3) = 4
  6. i=5, nums[5]=2: currentSum = max(2, 3+2) = 5, maxSum = max(4, 5) = 5
  7. i=6, nums[6]=1: currentSum = max(1, 5+1) = 6, maxSum = max(5, 6) = 6
  8. i=7, nums[7]=-5: currentSum = max(-5, 6-5) = 1, maxSum = max(6, 1) = 6
  9. i=8, nums[8]=4: currentSum = max(4, 1+4) = 5, maxSum = max(6, 5) = 6
  10. Return maxSum = 6

Hints

Hint 1
Think about using Kadane's algorithm.
Hint 2
At each position, you have two choices: start a new subarray or extend the current subarray.
Hint 3
Keep track of the maximum sum ending at the current position.

Video Tutorial

Maximum Subarray - Kadane's Algorithm

YouTube•Learn the Maximum Subarray solution step-by-step

Video tutorials can be a great way to understand algorithms visually

Visualization

Visualize the array and the maximum subarray that's found as the algorithm progresses.

Key visualization elements:

  • current element
  • current subarray
  • maximum subarray

Similar Questions

Maximum Product Subarray

Medium

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product. The test cases are generated so that the answer will fit in a 32-bit integer. A subarray is a contiguous subsequence of the array.

Asked By

MicrosoftAmazonAppleLinkedInFacebookGoogle

Implementation Notes

This problem demonstrates various approaches to the maximum subarray problem. Kadane's algorithm is the most efficient for this specific problem, but understanding the divide-and-conquer approach is valuable for similar problems.