Programming
In this programming tutorial we will try to solve maximum subarray problem using Kadane's algorithm.
Related: Maximum subarray problem - simple approach.
Given an array of N numbers (positive, negative or zero) find the sum of the largest contiguous subarray.
Input:
[1, 2, 4, -3]
We will find the sum of the largest contiguous subarray using Kadane's Algorithm by calculating the maximum sum at a given position by using the maximum sum at a previous position.
Steps:
Calculation +---------------+---------+ | Variables | Sum | +---------------+---------+ | current_sum | 0 | | max_sum | -1e18 | +---------------+---------+ | i = 0 | | | array[i] = 1 | | | current_sum | 1 | | max_sum | 1 | +---------------+---------+ | i = 1 | | | array[i] = 2 | | | current_sum | 3 | | max_sum | 3 | +---------------+---------+ | i = 2 | | | array[i] = 4 | | | current_sum | 7 | | max_sum | 7 | +---------------+---------+ | i = 3 | | | array[i] = -3 | | | current_sum | 4 | | max_sum | 7 | +---------------+---------+
Python
numbers = [1, 2, 4, -3] n = len(numbers) max_sum = -1e18 current_sum = 0 for i in range(n): current_sum += numbers[i] if current_sum > max_sum: max_sum = current_sum if current_sum < 0: current_sum = 0 print(max_sum)
7
Time complexity for this is O(n) which is better than the one we saw in the simple approach which had O(n2).
O(n)
O(n2)