Could you confirm that linear algorithm is not so wide solution like O(n log n) - divide and conquer ?
Because I have noticed that ,when all negative, it does not work.
But, in John Bentley "Programming Pearls" book there is not mention about working correctly only with positive.
int maxsofar = 0;
int maxhere = 0;
for (int j = 0; j < n; j++)
maxhere = mymax(maxhere + a[j], 0);
maxsofar = mymax(maxsofar, maxhere);