For starters, most candidates couldn't even get past an o(n) = n^2 brute force solution, let alone a solution that was n log n or simply o(n)=n in efficiency...
The problem: you have a sequence of integers that is alternating in sign.....Write an algorithm to find the largest consecutive sequence of integers that produces the largest sum.
For example: -1, 2, -5, 5,-3,2,-1,4,-3,4,-8,5,-5,8,-6
The answer would be: (assuming 0 indexed) n[3]...n[9] and the sum would be 8. ..... (5,-3,2,-1,4,-3,4)
The largest sum in the sequence is 8. It occurs twice in the set of numbers, but the largest sequence is n[3]-n[9], not just n[13]
The algorithm must return the indices of the sequence and the sum.
The ideal solution is o(n) =n in efficiency but a solution o(n) = n log n is fine
Computer language does not matter. Psuedo-code is fine.