mardi 1 juin 2010

Find subsequence with the maximum sum

[1, -2, 3, 5, 7] => [3,5,7]
[4, -2, 5] => [5]
[5, -6, 1, 2, 3, 4] => [1,2,3,4]
Solution:
def max_sum_subseq(arr):
    max_sum = 0
    max_start_index = 0
    max_length = 0
    current_sum = 0
    current_start_index = 0
    
    for i in range (0,len(arr)):
        if current_sum == 0 and arr[i] > 0:
             current_start_index = i
             
        current_sum += arr[i]
        if current_sum <= 0:
              current_sum = 0
              continue
       
        if current_sum >= max_sum:
            max_sum = current_sum
            max_length = i - current_start_index + 1
            max_start_index = current_start_index