Maximum Subarray

LeetCode 53 | Difficulty: Medium

Medium

Problem Description

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^5`

- `-10^4 <= nums[i] <= 10^4`

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.

Topics: Array, Divide and Conquer, Dynamic Programming

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

---

Solutions

Solution 1: C# (Best: 92 ms)

Metric	Value
Runtime	92 ms
Memory	26.3 MB
Date	2020-10-12

Solution

public class Solution {
    public int MaxSubArray(int[] nums) {
    int sum=nums[0], best =nums[0];
    int start=0, end=0, beg=0;
    for (int i = 1; i < nums.Length; i++)
    {
        sum = sum+nums[i];
        if(sum<=nums[i]){
            sum=nums[i];
            beg = i;
        }
        if(best<sum)
        {
            best=sum;
            start = beg;
            end=i;
        }
        
    }
    return best;
    }
}

📜 3 more C# submission(s)

Submission (2020-11-23) — 96 ms, 25.9 MB

public class Solution {
    public int MaxSubArray(int[] nums) {
        int len = nums.Length;
        if(len == 0)
            return 0;
        int max_so_far = nums[0];
        int max_cur = 0;
    
        for (int i = 0; i < len; i++)
        {
            max_cur = max_cur + nums[i];
            if(max_so_far < max_cur)
            {
                max_so_far = max_cur;
            }
            if(max_cur < 0)
            {
                max_cur = 0;
            }
        }
        return max_so_far;
    }
}

Submission (2017-10-21) — 166 ms, N/A

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max_ending_here = nums[0], max_so_far = nums[0];
    int pos_sum = Math.Max(0, nums[0]);
    for (int i = 1; i < nums.Length; i++)
    {
        max_ending_here = Math.Max(nums[i], max_ending_here + nums[i]);
        max_so_far = Math.Max(max_so_far, max_ending_here);
        pos_sum += Math.Max(nums[i], 0);
    }
    if (pos_sum == 0 && nums.Length > 0) pos_sum = nums.Max();
    return max_so_far;
    }
}

Submission (2020-04-04) — 208 ms, 24.8 MB

public class Solution {
    public int MaxSubArray(int[] nums) {
        int max_ending_here = nums[0], max_so_far = nums[0];
    int pos_sum = Math.Max(0, nums[0]);
    for (int i = 1; i < nums.Length; i++)
    {
        max_ending_here = Math.Max(nums[i], max_ending_here + nums[i]);
        max_so_far = Math.Max(max_so_far, max_ending_here);
        pos_sum += Math.Max(nums[i], 0);
    }
    if (pos_sum == 0 && nums.Length > 0) pos_sum = nums.Max();
    return max_so_far;
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.