Geek Culture
Published in

Geek Culture

tomroth.com.au

Kadane’s Algorithm — Python

Approach to solve subarray problems in a single pass and constant space.

The number of subarrays of an array with at least one element is N*(N + 1)/2. So if we have a problem where we need to check all subarrays for max, min, etc, we can use Kadane’s Algorithm since it achieves the max/min on subarray in a single pass.

In this algorithm, we traverse the given array from left to right. In the ith step, we apply the function on the subarray ending at i. Based on the chosen update criteria we decide to update the overall result with the current subarray result. In the case of the maximum sum scenario update criteria becomes max_sum < curr_sum. This approach can be applied to other problems as well by simply changing the update criteria.

It resembles the dynamic programming approach on the 1D array. Here also we compute the max/min at the current position based on the computed value of max/min at a previous position. It also resembles the Greedy approach since we reset the running sum/max/min whenever reaches the break condition.

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

Problem 1

Given an integer array, find the largest sum of the subarray having only non-negative elements.

Input: nums = [1, 4, -3, 9, 5, -6]
Output: 14
Explanation:
Subarray [9, 5] is the subarray having maximum sum with all non-negative elements.

Code Implementation

def max_sum_non_negs(nums):
max_sum = -math.inf
curr_max = 0

for num in nums:
if num < 0:
curr_max = 0
else:
curr_max += num

if max_sum < curr_max:
max_sum = curr_max

return max_sum
print(max_sum_non_negs([1, 4, -3, 9, 5, -6]))

Problem 2

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

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, -2, 5]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Code Implementation

def max_sum_sub_array(nums):
max_sum = -math.inf
curr_max = 0

for num in nums:
curr_max += num

if (max_sum < curr_max):
max_sum = curr_max

if (curr_max < 0):
curr_max = 0

return max_sum

print(max_sum_sub_array([-2, 1, -3, 4, -1, 2, 1, -5, -2, 5]))

Problem 3

Given an integer array nums, find the subarray (containing at least one number) which has the smallest sum.

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [-5] has the smallest sum = -5.

Code Implementation

def min_sum_sub_array(nums):
min_sum = math.inf
curr_min = math.inf

for num in nums:
if curr_min <= 0:
curr_min += num
else:
curr_min = num

if min_sum > curr_min:
min_sum = curr_min

return min_sum
print(min_sum_sub_array([-2,1,-3,4,-1,2,1,-5,4]))

Problem 4

Given a binary string of 0s and 1s. The task is to find the length of the substring which is having a maximum difference between the number of 0s and the number of 1s (number of 0s — number of 1s). In case of all 1s print -1.

Input : S = "11000010001"
Output : 6
From index 2 to index 9, there are 7 0s and 1 1s, so number of 0s - number of 1s is 6.

Code Implementation

def max_difference(s):
max_diff = -math.inf
curr_diff = 0

for digit in s:
if digit == '0':
curr_diff += 1
else:
curr_diff -= 1

if max_diff < curr_diff:
max_diff = curr_diff

if curr_diff < 0:
curr_diff = 0

return max_diff
print(max_difference("11000010001"))

Problem 5

Given an array of N positive integers, find the subarray having the maximum sum among all subarrays having unique elements.

Input nums = [1, 2, 3, 3, 4, 5, 2, 1]
Output: 15
Explanation:
The subarray having maximum sum with distinct element is [3, 4, 5, 2, 1] and it's sum is = 3 + 4 + 5 + 2 + 1 = 15

Code Implementation

def max_sum_unique(nums):
d = {}
max_sum = -math.inf
curr_max = 0

for num in nums:
if num not in d:
curr_max += num
d[num] = 1

if curr_max > max_sum:
max_sum = curr_max

if curr_max < 0:
curr_max = 0

return max_sum
print(max_sum_unique( [ 1, 2, 3, 1, 5 ]))

Problem 6

You are given an array prices where prices[i] is the price of a given stock on the ith day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5

Code Implementation

def max_profit(prices):
max_profit = 0
curr_profit = 0

for i in range(1, len(prices)):
curr_profit += prices[i] - prices[i-1]

if curr_profit < 0:
curr_profit = 0

if max_profit < curr_profit:
max_profit = curr_profit

return max_profit
print(max_profit([7, 1, 5, 3, 6, 4]))

Problem 7

Given an integer array, find a subarray within the array that has the largest product. Return the largest product

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Code Implementation

def max_product(nums):
cur_max = 1
cur_min = 1
max_prod = -math.inf

for n in nums:
cur_max, cur_min = max(cur_max * n, cur_min * n, n), min(cur_min * n, cur_max * n, n)
max_prod = max(max_prod, cur_max, cur_min)

return max_prod

print(max_product([2,3,-2,4]))
print(max_product([2,3,-2,4, -1]))

In all the above problems we could also find the indices of the subarray. Also, we can apply Kadane’s algorithm to the 2D matrix as well.

Happy Coding!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store