🤖
Data Structures and Algorithms
  • CS Theory And Problems
  • Big O
    • Big O Notation
  • Algorithms
    • Binary Search
    • Breadth First Search (BFS)
    • Depth First Search (DFS)
    • Dynamic Programming
    • Kadane's Algorithm
    • Kahn's Algorithm
    • Quickselect
    • Recursion
    • Sorting Algorithms
    • Sliding Window
  • Data Structures
    • Binary Heap
    • Graph
    • Linked List
    • Trees
  • Problems
    • LeetCode
      • 1. Two Sum
      • 3. Longest Substring Without Repeating Characters
      • 5. Longest Palindromic Substring
      • 11. Container With Most Water
      • 15. 3 Sum
      • 19. Remove Nth Node From End of List
      • 20. Valid Parentheses
      • 33. Search in Rotated Sorted Array
      • 49. Group Anagrams
      • 53. Maximum Subarray
      • 55. Jump Game
      • 56. Merge Intervals
      • 76. Minimum Window Substring
      • 98. Validate Binary Search Tree
      • 105. Construct Binary Tree from Preorder and Inorder Traversal
      • 121. Best Time to Buy and Sell Stock
      • 133. Clone Graph
      • 141. Linked List Cycle
      • 152. Maximum Product Subarray
      • 153. Find Minimum in Rotated Sorted Array
      • 200. Number of Islands
      • 206. Reverse Linked List
      • 207. Course Schedule
      • 217. Contains Duplicate
      • 226. Invert Binary Tree
      • 238. Product of Array Except Self
      • 242. Valid Anagram
      • 297. Serialize and Deserialize Binary Tree
      • 347. Top K Frequent Elements
      • 417. Pacific Atlantic Water Flow
      • 424. Longest Repeating Character Replacement
      • 435. Non-overlapping Intervals
      • 647. Palindromic Substrings
Powered by GitBook
On this page
  • Description
  • Examples
  • Solution
  • Brute Force
  • Kadane's Algorithm
  • Resources
  • Example Problem
  1. Algorithms

Kadane's Algorithm

Description

Kadane's algorithm solves the maximum subarray problem: given an array of n values (which can be positive, negative, or zero) find a contiguous subarray which has the maximum sum.

Kadane's original algorithm allows for empty subarrays (according to wikipedia). It will return 0 for an empty input array and for an array that contains only negative numbers.

Examples

input array
max sum
sub array

[2, 3, -6, 1, 5, 3]

9

[1, 5, 3]

[-2, 1, -3, 4, -1, 2, 1, -5, 4]

6

[4, -1, 2, 1]

[1]

1

[1]

[5, 8, -15, -3, 7, 4, 2])

13

[5, 8] or [7, 4, 2]

[-5, -2, -8, -1, -7]

0

[]

[2, 3, 4, 5, 6]

20

[2, 3, 4, 5, 6]

[]

0

[]

Notes from the above examples:

  • A negative number that causes the sum to be less than or equal to zero will not be part of the solution. See the first example.

  • A negative number that results with a sum that is greater than zero may or may not be part of the solution. See the second example.

  • An input array with just one element has a solution that is just that one element. See the third example

  • An input array may have more than one subarray with the same sum. See example 4.

  • An array that contains all negative numbers will have a solution of 0. See the fifth example.

  • An array that contains all positive numbers will have a solution that is the sum of the entire array. See the sixth example.

  • An empty array will have a solution of 0. See the sixth example.

Solution

Brute Force

The brute force solution is to sum the elements for every subarray in the array. Give an array of [2, 3, -6, 4], then the brute force algorithm would do the following:

  • Calculate the sum of array [2]

  • Calculate the sum of array [2, 3]

  • Calculate the sum of array [2, 3, -6]

  • Calculate the sum of array [2, 3, -6, 4]

  • Calculate the sum of array [3]

  • Calculate the sum of array [3, -6]

  • Calculate the sum of array [3, -6, 4]

  • Calculate the sum of array [-6]

  • Calculate the sum of array [-6, 4]

  • Calculate the sum of array [4]

An example implementation is below:

 class Solution:
     def max_sub_array_brute(self, nums: List[int]) -> int:
        high_sum = 0
        for i in range(len(nums)):
            current_sum = 0
            for j in range(i, len(nums)):
                current_sum += nums[j]
                if current_sum < 0:
                    current_sum = 0
                high_sum = max(high_sum, current_sum)
        return high_sum

Time complexity is O(N^2). Space complexity is O(1).

Kadane's Algorithm

The brute force solution is not efficient because it recalculates portions of the subarrays multiple times. In the above example [-6,4] is calculated as part of [2, 3, -6, 4], [3, -6, 4] and [6,4].

Kadane's algorithm iterates over the input array. It keeps track of two things: the maximum sum to this point and the current sum of the sub array.

At each element it compares if the current sum (which includes the current element) is less than 0. It may be less than zero if a negative number has caused it to become negative (ex: the -10 in this array[2, 4, -10, 3]). Otherwise the current sum is the sum of the sub array. The maximum sum is either the stored maximum sum or the new current sum.

class Solution:
    def max_sub_array_Kadane(self, nums: List[int]) -> int:
        high_sum = 0
        current_sum = 0
        for i in nums:
            current_sum = max(0, current_sum + i)
            high_sum = max(high_sum, current_sum)
        return high_sum

Time is O(N) and space is O(1).

Why does this work? When we are at iteration "i" the current_sum will contain the cumulative sum from A[a]+...+A[i-1]. We then assign current_sum to either 0 or current_sum + i. So, current_sum will always have the sum to this position, or it will have restarted. Then high_sum tracks the max value seen to that point.

Resources

Example Problem

PreviousDynamic ProgrammingNextKahn's Algorithm

Last updated 3 years ago

https://en.wikipedia.org/wiki/Maximum_subarray_problem
https://cs.slu.edu/~goldwamh/courses/slu/csci314/2012_Fall/lectures/maxsubarray/
https://www.researchgate.net/publication/222665016_Efficient_Algorithms_for_the_Maximum_Subarray_Problem_by_Distance_Matrix_Multiplication
Maximum Subarray