# Algorithm for calculating largest contiguous segment sum saving one
# more loop.


import sys, random, time

# Set up array of n random ints (including negatives)
n = int(sys.argv[1])
data = []

for i in range(n):
    data.append(random.randint(-1000,1000))

# Visualize data
if n <= 20:
    for i in range(n):
        print(data[i])

# Start timing
starttime = time.time()

# Start of main algorithm
maxsofar = 0
maxendinghere = 0 # the max sum for segments ending at [or more
                  # precisely: in the gap just after] the current
                  # position i
for i in range(n):
    # At this point, maxsofar and maxendinghere are correct for
    # data[0..i-1] and current position i-1
    maxendinghere = max(maxendinghere + data[i], 0)
    maxsofar = max(maxsofar, maxendinghere)
# Print final best segment sum
print(f"Max segment sum: {maxsofar}")

# End timing and print
print(f"Milliseconds: {(time.time() - starttime)*1000:.0f}")