🟨 Maximum Subarray (#53)
🔗 Problem Link
📋 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.
💡 Examples
Example 1
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.
Example 2
Input: nums = [1]
Output: 1
🔑 Key Insights & Approach
Core Observation: Kadane's Algorithm - keep running sum, reset to 0 if negative.
Why Kadane's?
- O(n) time, O(1) space
- Greedy: add current or start fresh
- Optimal and simple
Pattern: "Kadane's Algorithm" for maximum subarray.
🐍 Solution: Python
Approach: Kadane's Algorithm
Time Complexity: O(n) | Space Complexity: O(1)
from typing import List
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
max_sum = nums[0]
current_sum = 0
for num in nums:
current_sum = max(current_sum + num, num)
max_sum = max(max_sum, current_sum)
return max_sum
🔵 Solution: Golang
Approach: Kadane's Algorithm
Time Complexity: O(n) | Space Complexity: O(1)
func maxSubArray(nums []int) int {
maxSum := nums[0]
currentSum := nums[0]
for i := 1; i < len(nums); i++ {
currentSum = max(currentSum+nums[i], nums[i])
maxSum = max(maxSum, currentSum)
}
return maxSum
}
func max(a, b int) int {
if a > b { return a }
return b
}