# Maximum Sum Subsequence

17 Feb 2013The maximum sum subsequence of an array is the consecutive group of numbers that have the largest sum.

For example with the array `{1, 11, -9, -20, 7, 10, -6, 3, 4, -2}`

, the maximum sum subsequence is 18 using the elements `{7, 10, -6, 3, 4}`

starting from index `4`

and ending at index `8`

.

Here are a few algorithms implemented in Java of increasing efficiency that can be used to solve this problem.

1. **Brute Force -;** take each element as a starting point and each element after as an ending point, sum the elements in between and keep track of the largest sum.

**Efficiency (Order of Growth) = O(n^3)**

Although this works well, it scales extremely badly with the algorithm taking nearly half a second with only 2000 elements. As the size of the input doubles, the time taken will increase by a factor of 8 - not good.

2. **Remember the current sum.** Instead of computing the sum of elements i to j on each iteration of the innermost loop, we can instead remember the current sum of the elements. This increases the efficiency by a factor of O(n).

**Efficiency (Order of Growth) = O(n^2)**

This optimisation, although small saves a lot of execution time. Now as the size of the input array doubles, the time taken will increase by a factor of 4. However we can still improve this and gain a linear relationship between size and execution time.

3. **Single loop -;** now we only traverse the array once. We keep track of the maximal sum subsequence so far and the maximal sum subsequence ending at the current position.

**Efficiency (Order of Growth) = O(n)**

Now we have the best case scenario for this problem. We cannot get any better as in the worst case scenario each element of the array has to be looked at at least once. With the now linear order of growth as the size of the input doubles, the time taken also doubles.

Read More