#!/usr/bin/env python
# coding: utf-8

# # Το πρόβλημα της μέγιστης υποακολουθίας

# Τελευταία ενημέρωση: 2/10/2024

# In[1]:


def brute_force(a_list):
    """
    Find max subarray from a_list using brute force.
    """

    # initialize returns
    max_sum, start, end = a_list[0], 0, 0

    # brute force
    for i in range(len(a_list)):
        for j in range(i, len(a_list)):
            total = 0
            for x in range(i, j + 1):
                total += a_list[x]
            # replace start and end positions if a larger sum is found
            if max_sum < total:
                max_sum, start, end = total, i, j

    return max_sum, start, end


# In[2]:


get_ipython().run_cell_magic('timeit', '', 'import random\n\na_list = [random.randint(-100, 100) for _ in range(1000)]\nmax_sum, start, end = brute_force(a_list)\nprint(f"{max_sum=}, {start=}, {end=}")\n')


# In[4]:


def prefix_sums(a_list):
    """
    Find max subarray from a_list using prefix sums.
    """
    # initialize returns
    max_sum, start, end = a_list[0], 0, 0

    # prefix table generation
    prefix_table = list()
    for index, num in enumerate(a_list):
        prefix_table.append(num if index == 0 else num + prefix_table[index - 1])

    # use prefix table
    for i in range(len(a_list)):
        for j in range(i, len(a_list)):
            total = prefix_table[j] if i == 0 else prefix_table[j] - prefix_table[i - 1]
            # replace starting and ending positions if a larger sum is found
            if max_sum < total:
                max_sum, start, end = total, i, j

    return max_sum, start, end


# In[5]:


get_ipython().run_cell_magic('timeit', '', 'import random\n\na_list = [random.randint(-100, 100) for _ in range(1000)]\nmax_sum, start, end = prefix_sums(a_list)\nprint(f"{max_sum=}, {start=}, {end=}")\n')


# In[6]:


def kadane(a_list):
    """
    Find max subarray from a_list using kadane's algorithm (max suffix sums).
    """
    # initialize returns
    max_sum, start, end = a_list[0], 0, 0

    # generate kadane table
    kadane_table = list()
    for index, num in enumerate(a_list):
        total = num if index == 0 else num + kadane_table[index - 1]
        kadane_table.append(0 if total < 0 else total)

    # find max and ending position
    for index, total in enumerate(kadane_table):
        if max_sum < total:
            max_sum, end = total, index

    # find starting position
    for i in range(end, 0, -1):
        if kadane_table[i] == 0:
            start = i + 1
            break

    return max_sum, start, end


# In[8]:


get_ipython().run_cell_magic('timeit', '', 'import random\n\na_list = [random.randint(-100, 100) for _ in range(1000)]\nmax_sum, start, end = kadane(a_list)\nprint(f"{max_sum=}, {start=}, {end=}")\n')


# In[ ]: