Kadane's algorithm is specifically designed for Maximum/Minimum Sum Subarray problems and uses a Dynamic Programming approach.

Example: Maximum Subarray

1. On each index, it is calculating the best subarray which includes the index and tracking the max sum subarray.
2. If the current sum is negative, since it is not beneficial, abandon the current subarray and start from this new number.

func maxSubArray(nums []int) int {
	if len(nums) < 1 {
		return 0
	}

	sum := nums[0]
	maxSum := nums[0]
	for i := 1; i < len(nums); i++ {
		// if previous result isn't helping (negative value), start from the new subarray
		sum = max(sum, 0)
		sum += nums[i]

		// another representation
		// sum = max(sum+nums[i], nums[i])

		maxSum = max(maxSum, sum)
	}

	return maxSum
}

(Medium) 53. Maximum Subarray, NeetCode 75

https://leetcode.com/problems/maximum-subarray

The numbers include both positive and negative.

Last review: Jul 31, 2025 Next review: It was fine, but your confidence level wasn’t high. Explain it before you solve it.

Iteration (Brutal Force)

Try all subarrays

• Time Complexity O(n + n-1 + n-2 + … + n-(n-1)) = O(n*(n+1)/2) = O(n^2)
• Space Complexity O(1)

func maxSubArray(nums []int) int {
	if len(nums) < 1 {
		return 0
	}

	maxSum := nums[0]

	for L := 0; L < len(nums); L++ {
		var sum int
		for R := L; R < len(nums); R++ {
			sum += nums[R]
			maxSum = max(maxSum, sum)
		}
	}
	return maxSum
}

Prefix (Brutal Force)

Try all subarrays

• Time Complexity O(n + n-1 + n-2 + … + n-(n-1)) = O(n*(n+1)/2) = O(n^2)
• Space Complexity O(1)

func maxSubArray(nums []int) int {
	if len(nums) < 1 {
		return 0
	}

	prefix := make([]int, len(nums)+1) // 1-index-based
	maxSum := nums[0]

	for R := 0; R < len(nums); R++ {
		prefix[R+1] = prefix[R] + nums[R]
		// try subarrays starting before R
		for L := 0; L <= R; L++ {
			maxSum = max(maxSum, prefix[R+1]-prefix[L])
		}
	}

	return maxSum
}

DP (Kadane's) ⭐️