find sub sequence with largest sum in a sequence of numbers

sub_sequence.py

import random
import time


def timing(f):
    def wrap(*args):
        time1 = time.time()
        ret = f(*args)
        time2 = time.time()
        print('%s function took %0.3f ms' % (f.__name__, (time2-time1)*1000.0))
        return ret
    return wrap


li = [2, 5, -8, 3, 9, -2, -4, 0, 2, 6, -3, -5, 0, -4, 2, 3, 1]
l = [1, 2, 3, -5, 4, -5, 20]


def largest_sum_seq(li):
    res_i, res_x = 0, li[0]
    cur_i, cur_x = res_i, res_x
    for i in range(1, len(li)):
        cur_i += 1
        cur_x += li[i]
        if cur_x > res_x:
            res_i, res_x = cur_i, cur_x
    return res_i, res_x


assert(largest_sum_seq(l) == (6, 20))


@timing
def get_largest_sum_seq(li):
    n = len(li)
    max_x = 0
    max_from = 0
    max_to = 0
    for i in range(n - 1):
        curr_i, curr_x = largest_sum_seq(li[i:])
        if curr_x > max_x:
            max_x = curr_x
            max_from = i
            max_to = curr_i + 1
    return max_x, max_from, max_to


assert(get_largest_sum_seq(li) == (14, 3, 7))


@timing
def max_sum_subseq(li):
    best_start, best_length, max_sum = 0, 1, li[0]
    cur_start, cur_length, cur_sum = best_start, best_length, max_sum
    for i in range(1, len(li) - 1):
        if cur_sum < 0:
            cur_start, cur_length, cur_sum = i, 1, li[i]
        else:
            cur_length += 1
            cur_sum += li[i]
        if cur_sum > max_sum:
            best_start, best_length, max_sum = cur_start, cur_length, cur_sum
    return max_sum, best_start, best_length


assert(max_sum_subseq(li) == (14, 3, 7))


def rand_list(a, b, n):
    return [random.randint(a, b) for x in range(0, n)]


def test_times():
    li = rand_list(-10, 10, 10000)
    res = get_largest_sum_seq(li)
    print(res)
    res = max_sum_subseq(li)
    print(res)


test_times()


# get_largest_sum_seq function took 7514.040 ms
# (801, 1098, 8864)
# max_sum_subseq function took 1.660 ms
# (801, 1098, 8864)