List Subsequents Method

Question

So, I have to find the maximum Sum of the continuous subset, I followed this algorithm in python.

def SubSeq(list):
    final_list = None
    suming = 0
    for start in range(len(list)):
        for end in range(start+1, len(list)+1):
            subseq = list[start:end]
            summation= sum(list[start:end])
            if summation > suming:
                suming = summation
                final_list = subseq
    return final_list


print SubSeq([5, 15, -30, 10, -5, 40, 10])

I wonder if it is a correct way in dynamic programming though the running time is O(n^2). Plus, is there a possible way to make it O(n)

Answer 1

This is not Dynamic Programming, it is a brute force solution. The solution seems to be correct, but as you observer - it is inefficient.

An O(n) solution can be achieved by applying Dynamic Programming, denote D(i) as the maximum sub contiguous subarray that ends in i, and must include i.

D(-1) = 0
D(i) = max{ arr[i], D(i-1)

The idea is, you have two choices - get the previously "best" array that ends at i-1 and add element i to it, or create a new one that starts with i.

At the end, by applying the above in a DP solution, you get an array where each element indicates the maximum sub contiguous array ending with this index, all you have to do is choose the maximal value out of this array to get the value of the maximal sum, and go back on the array to get the actual subsequence.

---

Example:

array = 5,15,-30,10,-5,40,10

Applying the dynamic programming:

D(-1) = 0
D(0) = 5
D(1) = 20
D(2) = -10
D(3) 10 //because max{-10+10,10} = 10
D(4) = 5
D(5) = 45
D(6) = 55

And now you have the array:

D = [5,20,-10,10,5,45,55]

The maximal subsequence's value is 55, and is given by [10,-5,40,10] (following the above array, and going back on it)

Answer 2

You are basically calculating the sum again and again.You can avoid that by storing the sums in an array. You can do it in O(n).

Let S[0,1..n-1] be the sequence Let T[0,1,...n-1] be the array in which T[i] is the maximum continuous sum possible starting from ith element.

Now to fill T[i], start from reverse. T[n-1]=max(S[n-1],0)
Now T[i]=max(T[i+1]+S[i] , S[i] ,0)

Now go through the 'T' array to find the maximum sum.

Let T[m] be the max value.

To calculate the exact sequence start from S[m] and add all the elements till the sum equals T[m]