Calculate Profits faster than O(n!)

So last week I posted a problem for the ACM ICPC South East Regionals here -> Algorithm to calculate the number of 1s for a range of numbers in binary. It was pretty well recieved and still hasn't been solved so I figured why not throw up another question my team couldn't solve.

The Problem.

Your friends have just opened a new business, and you want to see how well tehy are doing. The business has been running for a number of days, and your friends have recorded their net profit on each day. You want to find the largest total profit that your friends have made during any consecutive time span of at least one day. For example, if your friends profits looked like this:

Day 1: -3
Day 2: 4
Day 3: 9
Day 4: -2
Day 5: -5
Day 6: 8

Their maximum profit over any span would be 14, from day 2 to 6.

Input

There will be several test cases in the input. Each test case will begin with an integer N ( 1 <= N <= 250,000) on its own line, indicating the number of days. On each of the next N lines will be a single integer P (-100 <= P <= 100), indicating the profit for that day. The days are specified in order. The input will end with a line with a single 0

Output

For each test case, output a single integer, representing the maximum profit over any non-empty span of time. Print each integer on its own line with no spaces. Do not print any plank lines between answers.

Sample Input

6
-3
4
9
-2
-5
8
2
-100
-19
0

Sample Output

14
-19

---

The code to solve this problem is pretty simple if you do not worry about efficiency but the only way it was solved at the contest was at O(n!), which is un-acceptable. I hope stack overflow can do better

Good luck!

EDIT

---

Just to keep this updated here is completed code that solves this problem in O(n).

import java.util.Scanner;

public class Profits { 
    public static int  seqStart=0, seqEnd=-1; 
    pub开发者_如何学Clic static void main(String args[]) { 
        Scanner s = new Scanner(System.in);
        while (s.hasNextLine()) {
            int current = s.nextInt();
            if (current == 0)
                break;
            else {
                int count = current;
                int[] a = new int[count];
                for (int x = 0; x < count; x++) {
                    a[x] = s.nextInt();
                }
                System.out.println(max_subarray(a));
            }
        }
    }       
    private static int max_subarray(int[] a) { 
        int maxSum = a[0], thisSum = a[0]; 
        for(int i=0, j=0;j<a.length;j++) { 
            thisSum = thisSum + a[j]; 
            if(thisSum > maxSum) { 
                maxSum = thisSum; 
                seqStart = i; 
                seqEnd = j; 
            } 
            else if (thisSum < 0) { 
                i = j+1; 
                thisSum = 0; 
            } 
        } 
        return maxSum; 
    }    
}

---

You're looking for the Maximum Subarray Problem.
It can be solved in O(n), as described by Wikipedia.