Teaching Kids Programming – Maximum Subarray by Dynamic Programming and Greedy 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

Maximum Subarray by Bruteforce Algorithm

We can iterate all pairs which takes O(N^2) time and then use linear O(N) algorithm to compute the sublist sum – which results in O(N^3) time. With an optimisation, we can reduce this to O(N^2) using a varaible to accumulate the sum while we iterate the pairs of sublists.

1
2
3
4
5
6
7
8
9

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

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

Dynamic Programming Algorithm to Compute the Maximum SubArray Sum

We can keep the sum of the current sublist – then we have two choices when considering the next element – we can pick the next element or start a new list with next element. This Dynamic Programming approach is also known as Kadane’s Algorithm.

1
2
3
4
5
6
7

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = c = nums[0]
        for i in nums[1:]:
            c = max(i, c + i)
            ans = max(ans, c)
        return ans

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        ans = c = nums[0]
        for i in nums[1:]:
            c = max(i, c + i)
            ans = max(ans, c)
        return ans

The time complexity is O(N) and space complexity is O(1) constant.

C++ Coding Exercise – Maximum Subarray (Dynamic Programming and Greedy Algorithm)

Maximum SubArray Sum via Greedy Algorithm

We can apply the greedy algorithm. When the sum is non-negative, we keep adding next numbers otherwise we choose next number as the new sublist sum:

1
2
3
4
5
6
7
8
9
10
11

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

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

The time complexity is O(N) where N is the number of elements in the list and the space complexity is O(1). This is the same complexity (both time and space) as the above Dynamic Programming Approach.

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) —