Geek Culture
Published in

Geek Culture

tomroth.com.au

Kadane’s Algorithm — Python

Complexity

Problem 1

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

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

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

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

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

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
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

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
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]))

--

--

A new tech publication by Start it up (https://medium.com/swlh).

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