prathji
BAN USER- 1of 1 vote
Answersfind nearest word from the given non-english dictionary which is one off character. (could be non ascii characters)
- prathji in United States
for eg. dictionary contains { apple, pineapple, banana, orange }
if given word "applx" then return true, as applx matches with apple and only one character is off.
aplpe returns false| Report Duplicate | Flag | PURGE
Google Software Developer
def maxProduct(self, nums):
min_product_till_now = float('inf')
max_product_till_now = -float('inf')
max_so_far = -float('inf')
for item in nums:
if item < 0:
t1 = max(min_product_till_now * item, item)
t2 = min(max_product_till_now * item, item)
elif item > 0:
t1 = max(max_product_till_now * item, item)
t2 = min(min_product_till_now * item, item)
else:
t1, t2 = 0, 0
min_product_till_now, max_product_till_now = t2, t1
max_so_far = max(t1, t2, max_so_far)
return max_so_far
This solution is a modification of Kadane's algorithm which maintains two different sums namely max_till_now and min_till_now which are maximum and minimum till the current index.
This could easily be changed to find the indices.
def three_subs(arr):
max_so_far = 0
max_till_now = 0
m = [0]
curr_index = 0
new_introduced = True
for item in arr:
max_till_now += item
if max_till_now < 0:
max_till_now = 0
if not new_introduced:
curr_index += 1
m.append(0)
new_introduced = True
else:
m[curr_index] = max(m[curr_index], max_till_now)
new_introduced = False
return m
arr = [-1, -2, 3, 4, 5, -700, 1, 2, 8, -100, 4, 5, -200, 99]
print three_subs(arr)
It is a small modification to Kadane's algo, I feel.
- prathji June 15, 2017
- prathji June 18, 2017