algoadvance

Leetcode 53. Maximum Subarray

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.

Example:

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

Constraints:

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

Clarifying Questions

1. Q: Can the input array be empty?
   • A: No, as per the constraints, the length of the array is at least 1.
2. Q: Are all elements integers?
   • A: Yes, all elements in the array are integers and fall within the range -10^4 to 10^4.
3. Q: Should we return the subarray itself, or just its sum?
   • A: The problem requires only the sum of the maximum subarray.

Strategy

To solve this problem efficiently, we can use Kadane’s Algorithm. This algorithm is based on dynamic programming and works as follows:

1. Initialize two variables: max_current and max_global. Set both to the first element of the array.
2. Iterate through the array starting from the second element:
   • Update max_current to be the maximum of the current element alone or the sum of max_current and the current element.
   • Update max_global to be the maximum of max_global and max_current.
3. After finishing the iteration, max_global will contain the largest sum of the contiguous subarray.

Code

public class Solution {
    public int maxSubArray(int[] nums) {
        int max_current = nums[0];
        int max_global = nums[0];
        
        for (int i = 1; i < nums.length; i++) {
            max_current = Math.max(nums[i], max_current + nums[i]);
            if (max_current > max_global) {
                max_global = max_current;
            }
        }
        
        return max_global;
    }
}

Time Complexity

• Time Complexity: O(n) where n is the length of the array. We only need to pass through the array once.
• Space Complexity: O(1). No additional space besides a few variables.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?