# 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:** 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_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 :** 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_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:** 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_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:** 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_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:** 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!!