Leetcode 53: Maximum Subarray

 

1. Problem Statement (Simple Explanation):

You are given an integer array nums.

You must find the contiguous subarray (containing at least one number) which has the largest sum, and return that sum.

2. Examples:

Example 1:

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

The subarray [4, -1, 2, 1] has sum 4 + (-1) + 2 + 1 = 6, which is the largest.

Output: 6

Example 2:

Input: nums = [1]

Only one subarray [1], sum = 1.

Output: 1

Example 3:

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

Best subarray is the whole array, sum = 5 + 4 + (-1) + 7 + 8 = 23.

Output: 23

3. Approach 1 – Kadane’s Algorithm (O(n), Standard):

This is the classic linear-time solution.

Intuition:

As you traverse the array, maintain:

• currentSum – maximum subarray sum ending at the current index.

• maxSum – maximum subarray sum seen so far.

For each nums[i], you decide:

• Either extend the previous subarray: currentSum + nums[i]

• Or start a new subarray from nums[i]

So:

currentSum = max(nums[i], currentSum + nums[i])

maxSum = max(maxSum, currentSum)

This works because a negative currentSum is harmful to any future subarray, so we drop it and restart when needed.

Pseudo-code (Kadane):

Complexity:

• Time: O(n)

• Space: O(1) extra

4. Approach 2 – Divide & Conquer (Follow-up):

High-level (not required but worth knowing):

• Divide array into two halves.

• Maximum subarray is either:

1. Entirely in the left half.

2. Entirely in the right half.

3. Crossing the middle.

Use recursion to combine these. This yields O(n log n) time. Kadane’s is simpler and optimal in practice.

5. Java code:

6. C code:

7. C++ code:

8. Python code:

9. JavaScript code: