class Solution(object):
def largestSum(self, array):
"""
input: int[] array
return: int
"""
curr_max = array[0]
global_max = curr_max
for i in range(1, len(array)):
# print("i is {0}".format(i))
# print("curr_max is {0}".format(curr_max))
if (curr_max + array[i] > array[i]):
curr_max = curr_max + array[i] # include this element as position i
else:
curr_max = array[i]
if curr_max > global_max:
global_max = curr_max
else:
continue
return global_max
Note the DP only stores global_max and curr_max
Be the first to comment
You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.