计算利润快于O(n!)

所以上周我在这里发布了一个ACM ICPC东南区域的问题-> Algorithm to calculate the number of 1s for a range of numbers in binary . 这是很好的接收,仍然没有解决,所以我想为什么不提出另一个问题,我的团队无法解决。

问题是。

你的朋友刚开了一家新公司,你想看看特希做得有多好。这家公司经营了好几天,你的朋友们每天都记录下他们的净利润。你想找到你的朋友在任何一个连续的至少一天的时间里所获得的最大的总利润。例如,如果你的朋友的利润是这样的:

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

他们在任何跨度的最大利润将是14,从第2天到6。

输入
输入中将有几个测试用例。每个测试用例将在其自己的行上以整数N(1<=N<=250000)开头,指示天数。接下来的N行中的每一行都是一个整数P(-100<=P<=100),表示当天的利润。日期是按顺序指定的。输入将以一行0结尾

输出
对于每个测试用例,输出单个整数,表示在任何非空时间跨度上的最大利润。将每个整数打印在自己的行上,不带空格。不要在答案之间打印任何木板线。

样本输入

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

样本输出

14
-19

如果你不担心效率的话,解决这个问题的代码是非常简单的,但是在比赛中解决这个问题的唯一方法是在O(n!),这是不可接受的。我希望堆栈溢出能做得更好

祝你好运!

编辑

为了保持这个更新,这里是完整的代码,它在O(n)中解决了这个问题。

import java.util.Scanner;

public class Profits { 
    public static int  seqStart=0, seqEnd=-1; 
    public 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; 
    }    
}