Maximum Subarray Problem - Brute Force (O(n^2) v1).py

import time
import random
import sys

print("Αλγόριθμος BruteForce2.0 --> O(n^2)")
print("Θα δημιουργήσουμε δύο λίστες, η μία με διπλάσιο αριθμό στοιχείων από την άλλη, με seed τον ΑΜ και τιμές στο διάστημα (-100, 100)")
print("Επιλέξτε 1 για λίστες 5000 και 10000 στοιχείων αντιστοίχως.")
print("Επιλέξτε 2 για να καθορίσετε τον αριθμό στοιχείων")

#Καθορισμός μεγέθου λίστας
e = int(input("Επιλογή:" ))
if e==1:
    num=5000
elif e==2:
    print("Επιλογή αριθμού στοιχείων. Για παράδειγμα, επιλέξτε 100 για να δημιουργήσετε δύο λίστες των 100 και των 200 στοιχείων αντιστοίχως.")
    num=int(input("Επιλογή:" ))
else:
    print("Δεν υπάρχει αυτή η επιλογή! Ξαναπροσπαθήστε...")
    sys.exit()
    

#Συνάρτηση που δημιουργεί την λίστα με seed τον ΑΜ
random.seed(1053711)
def makeArr(num, maxn):
    arr = [0]*num                              #Δημιουργώ μία κενή λίστα με το δοσμένο μέγεθος
    for i in range (num):                      #Την γεμίζω με τυχαίους αριθμούς στο δοσμένο διάστημα
        arr[i] = random.randint(-maxn, maxn)
    return arr

arr = makeArr(num,100)
double_arr = makeArr(2*num, 100)


#Συνάρτηση που υπολογίζει το μέγιστο υποάθροισμα
def bf2a(arr):
    n = len(arr)                        #Μήκος λίστας
    m = (0, 0, 0)
    for i in range (n):                 #Πρώτο σκανάρισμα της λίστας
        s=0                             #Διατηρείται το άθροισμα, όσο το j αυξάνεται
        for j in range (i+1,n+1):       #Δεύτερο σκανάρισμα της λίστας
            s += arr[j-1]
            if s > m[0]:
                m = (s, i, j)           #Καταχώρηση αποτελέσματος αν είναι καλυτερο από το προηγούμενο
    return m                            #Επιστρέφει το αποτέλεσμα

print("Γίνεται υπολογισμός...")
to = time.time()                        #Αρχή πρώτης χρονομέτρησης
m = bf2a(arr)                           #Υπολογισμός μέγιστου υποαθροίσματος πρώτου πίνακα
t1 = time.time()                        #Τέλος πρώτης χρονομέτρησης, αρχή δεύτερης χρονομέτρησησς                       
d = bf2a(double_arr)                    #Υπολογισμός μέγιστου υποαθροίσματος δεύτερου πίνακα
t2 = time.time()                        #Τέλος δεύτερης χρονομέτρησης

print("Μέγιστο υπό-άθροισμα λίστας", num,"στοιχείων:", m[0])
print("Θέση αρχής μέγιστης υπό-λίστας:", m[1],". Θέση τέλους μέγιστης υπό-λίστας:", m[2],".")
print("Χρόνος υπολογισμού:",t1 - to,'seconds')
print("Μέγιστο υπό-άθροισμα λίστας", 2*num,"στοιχείων:", d[0])
print("Θέση αρχής μέγιστης υπό-λίστας:", d[1],". Θέση τέλους μέγιστης υπό-λίστας:", d[2],".")
print("Χρόνος υπολογισμού:",t2 - t1,'seconds')