Published in

Geek Culture

# 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_sumprint(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: 6Explanation: [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: 6Explanation: [-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_sumprint(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 : 6From 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_diffprint(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: 15Explanation: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_sumprint(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: 5Explanation: 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_profitprint(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: 6Explanation: [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!!

--

--