LeetCode Problem 53: Maximum Subarray – Java Solution Using Kadane’s Algorithm

Struggling with the Maximum Subarray problem on LeetCode? This guide introduces Kadane’s Algorithm, an efficient method to find the largest sum of a contiguous subarray in linear time. Ideal for coding interviews and practical applications.

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: The subarray [4,-1,2,1] has the largest sum = 6.

Why Kadane’s Algorithm?

Kadane’s Algorithm is optimal for this problem because:

Linear Time Complexity: Traverses the array once, resulting in O(n) time complexity.
Constant Space: Utilizes only a few variables, achieving O(1) space complexity.
Handles Various Cases: Effectively manages arrays with negative numbers and varying lengths.

Java Solution Code

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

Step-by-Step Explanation

Initialize Variables:
- currentSum: Tracks the sum of the current subarray. Initialize to nums[0].
- maxSum: Records the maximum subarray sum found so far. Also starts at nums[0].
Iterate Through the Array:
- For each element from index 1 onward:
  - Update currentSum: Decide whether to add the current element to the existing subarray or start a new subarray with the current element. currentSum = Math.max(nums[i], currentSum + nums[i]);
  - Update maxSum: Compare currentSum with maxSum and update maxSum if currentSum is greater.
Return Result:
- After processing all elements, maxSum contains the largest sum of any contiguous subarray.

Complexity Analysis

Time Complexity: O(n), where n is the length of nums. The algorithm makes a single pass through the array.
Space Complexity: O(1), as it uses a constant amount of extra space.

Key Takeaways

Efficient Subarray Sum Calculation: Kadane’s Algorithm provides a streamlined approach to finding the maximum subarray sum with minimal computational overhead.
Versatility: Effectively handles arrays with mixed positive and negative numbers.
Practical Applications: Useful in various fields such as financial analysis (e.g., determining maximum profit segments) and image processing.

Frequently Asked Questions (FAQs)

Q1: What if the array contains all negative numbers?

Kadane’s Algorithm will return the largest (least negative) number, as including any additional elements would decrease the sum.

Q2: Can this problem be solved using a different approach?

Yes, a divide-and-conquer method can solve this problem with O(n log n) time complexity, but Kadane’s Algorithm is more efficient with O(n) time complexity.

Q3: How can I modify the algorithm to return the subarray itself?

By keeping track of the start and end indices whenever currentSum is updated, you can extract the subarray with the maximum sum.

Q4: Is Kadane’s Algorithm applicable to multidimensional arrays?

Kadane’s Algorithm is primarily designed for one-dimensional arrays. Extensions exist for multidimensional cases but are more complex.