Programming Praxis

We’ll categorize today’s exercise as part of our on-going series of interview questions, but it’s really more than that:

Given a sequence of integers, both positive and negative, find the contiguous subsequence with the maximum sum. For instance, given the sequence 31, -41, 59, 26, -53, 58, 97, -93, -23, 84, the maximum sum subsequence is 59, 26, -53, 58, 97, which sums to 187.

Your task is to write a series of functions that takes a sequence (use either a list or an array, whichever is convenient for your programming language) and returns the sum of the maximum sum subsequence; you should find solutions with time complexities of O(n³), O(n²), O(n log n), and O(n). When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2