Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution

Problem Statement

Given an integer array nums, find the contiguous subarray (containing at least one number) that has the largest sum and return its sum.

Intuition

The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm, which efficiently finds the maximum sum subarray in O(n) time.

Approach

• Initialize two variables: total (running sum) and maxi (maximum sum encountered so far).
• Iterate through the array:
  • Add the current element to total.
  • Update maxi with the maximum of maxi and total.
  • If total becomes negative, reset it to zero.
• Return maxi as the maximum subarray sum.

Code Implementation

        
import sys
from typing import List

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        total = 0
        maxi = -sys.maxsize - 1
        for i in range(n):
            total += nums[i]
            maxi = max(maxi, total)
            if total < 0:
                total = 0
        return maxi
        
    

Complexity Analysis

• Time Complexity: O(n) since we iterate through the array once.
• Space Complexity: O(1) as we use only a few extra variables.

Example Walkthrough

Example 1

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

Index	nums[i]	total	maxi
0	-2	-2	-2
1	1	1	1
2	-3	-2	1
3	4	4	4
4	-1	3	4
5	2	5	5
6	1	6	6
7	-5	1	6
8	4	5	6

Output: 6 (subarray [4,-1,2,1] has the largest sum)

Edge Cases Considered

• Single-element arrays (e.g., [1], [-1]).
• All negative numbers (Kadane’s algorithm ensures the maximum negative number is chosen).
• Arrays with zeros.
• Large input sizes for performance verification.

Conclusion

Kadane’s Algorithm is an optimal and simple approach to solving this problem in linear time with constant space. It efficiently determines the maximum sum of any contiguous subarray in an input array.

Further Reading

For more details and discussion, check out my solution on LeetCode:
Kadane's Algorithm - Maximum Subarray Problem