Teaching Kids Programming – Max Subarray Sum by Kadane’s Algorithm

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

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

Example 3:
Input: nums = [5,4,-1,7,8]
Output: 23

Bruteforce Algorithm to Compute the Maximum Subarray Sum

We can bruteforce all subarrays and that is going to take O(N^2) and then we need O(N) to call sum on the subarray – overall it is O(N^3) time complexity:

1
2
3
4
5
6
7
8
9

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        assert n > 0
        ans = -math.inf
        for L in range(n):
            for R in range(L, n) :
                ans = max(ans, sum(nums[L: R+1]))
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        assert n > 0
        ans = -math.inf
        for L in range(n):
            for R in range(L, n) :
                ans = max(ans, sum(nums[L: R+1]))
        return ans

Improved Bruteforce Algorithm to Compute the Maximum Subarray Sum

We don’t need to compute the sum of subarray every time, we can accumulate the sum, that will give us O(N^2):

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        assert n > 0
        ans = -math.inf
        for L in range(n):
            s = 0
            for R in range(L, n) :
                s += nums[R]
                ans = max(ans, s)
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        assert n > 0
        ans = -math.inf
        for L in range(n):
            s = 0
            for R in range(L, n) :
                s += nums[R]
                ans = max(ans, s)
        return ans

A litter bit faster, but still slow.

Kadane’s Algorithm (Iterative Dynamic Programming) to Compute Maximum Sum of Subarray

Kadane’s Algorithm is an optimal Iterative Dynamic Programming Algorithm to compute the Maximum SubArray Sum of one dimensional array in linear time. Its core idea is based on the following:

where d(i) is the max sum of subarray that ends at index i, and then n[i] is the number at index i. At each index, we can choose to use previous subarray sum at d(i-1) or we can choose to ignore and start a new subarray with current single number.

1
2
3
4
5
6
7
8
9

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:       
        s = 0
        assert len(nums) > 0
        ans = -math.inf
        for i in nums:
            s = max(s + i, i)
            ans = max(ans, s)                
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:       
        s = 0
        assert len(nums) > 0
        ans = -math.inf
        for i in nums:
            s = max(s + i, i)
            ans = max(ans, s)                
        return ans

The time complexity is O(N) and the space complexity is O(1) constant as when we compute d(i) we only require d(i-1) which we can solve using two variables (iteratively).

Maximum Subarray Sum Algorithms

• Teaching Kids Programming – Maximum Subarray by Dynamic Programming and Greedy Algorithm
• Compute the Maximum Subarray via Dynamic Programming or Greedy Algorithms
• Teaching Kids Programming – Max Subarray Sum by Kadane’s Algorithm

–EOF (The Ultimate Computing & Technology Blog) —