# Algorithm for calculating largest contiguous segment sum, with one
# loop collapsed.

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
# For all segment starting points
for i in range(n):
    sum = 0 # start with the empty segment
    #For all segment ending points
    for j in range(i,n):
        # Expand the previous segment with data[j]
        sum += data[j]
        # Update best known segment sum
        maxsofar = max(maxsofar, sum)
# Print final best segment sum
print(f"Max segment sum: {maxsofar}")

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