Most of the answers here are wrong (or perhaps the question is wrong, and a subarray is actually wanted instead). In a subsequence, the array elements do not have to be contiguous, hence simply sum up all the positive numbers in the array.

Assuming that array contains positive or negative real numbers. (If numbers are only positive, max sum subsequence is obviously the entire array) O(n log n) divide-and-conquer solution outline: 1. Recursively halve the array into array slices of unit 1. 2. Merge array slices, maintaining the totals and start/end indices of 4 types of subsequences: subsq1. The subsequence that contains the greatest sum within the slice subsq2. The subsequence that contains the greatest sum within the slice and that ends at the rightmost cell of the slice subsq3. The subsequence that contains the greatest sum within the slice and starts at the leftmost cell of the slice subsq4. The entire slice While merging 2 slices together update these slices as follows, 1. max(leftSlice.subsq1, rightSlice.subsq1, leftSlice.subsq2 + rightSlice.subsq3) 2. max(rightSlice.subsq2, leftSlice.subsq2 + rightSlice.subsq4) 3. max(leftSlice.subsq3, rightSlice.subsq3 + leftSlice.subsq4) 4. leftSlice.subsq4 + rightSlice.subsq4 When all the array slices are merged, subsq1 will give you the greatest subsequence. We cannot do better than O(n) because we will have to access each element. We probably cannot do better than O(n log n) because we will have to eventually compare subsequence candidates.

see Wikipedia...