# Basic algorithm for calculating largest contiguous segment sum

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 subsegments
for i in range(n):
    for j in range(i,n):
        # Sum the segment
        sum = 0
        for k in range(i, j+1):
            sum += data[k]
        # 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}")