Find max sum of sub sequence

max_sum_of_sub_sequence.py

def find_max_sum_of_sub_sequence(seq, start, end):
    if end - start == 0:
        return seq[start], start, end
    else:
        mid = (start + end) / 2
        left_max, left_start, left_end = find_max_sum_of_sub_sequence(seq, start, mid)
        right_max, right_start, right_end = find_max_sum_of_sub_sequence(seq, mid + 1, end)

        i = mid
        mark_i = i
        left_sum, max_left_sum = 0, seq[i]
        while i >= start:
            left_sum += seq[i]
            if left_sum > max_left_sum:
                max_left_sum = left_sum
                mark_i = i
            i -= 1

        j = mid + 1
        mark_j = j
        right_sum, max_right_sum = 0, seq[j]
        while j < end:
            right_sum += seq[j]
            if right_sum > max_right_sum:
                max_right_sum = right_sum
                mark_j = j
            j += 1

        max_value = max([left_max, right_max, max_left_sum + max_right_sum])
        if max_value == left_max:
            return max_value, left_start, left_end
        elif max_value == right_max:
            return max_value, right_start, right_end
        elif max_value == max_left_sum + max_right_sum:
            return max_value, mark_i, mark_j


def main():
    sequence = [1, 23, -100, 8, 9, 0, -2, -3, 78, 89, 20, -5, -1, -5, 43, 20, 9, 4, -3, -20, 28]
    mx = find_max_sum_of_sub_sequence(sequence, 0, len(sequence) - 1)
    print(mx)


if __name__ == '__main__':
    main()