比O(n!)更快地计算利润

Question

所以上周我在这里为ACM ICPC东南地区发布了一个问题 - > 算法来计算二进制数字范围的1的数量.收到的很好,但仍然没有解决,所以我想为什么不提出我的团队无法解决的另一个问题.

问题.

你的朋友刚刚开了一家新公司,你想看看tehy做得多好.这项业务已经运行了好几天,你的朋友每天都记录了他们的净利润.您希望找到朋友在至少一天的连续时间段内获得的最大总利润.例如,如果您的朋友的利润看起来像这样:

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

从第2天到第6天,他们在任何跨度上的最大利润为14.

输入输入
中将有几个测试用例.每个测试用例将在其自己的行上以整数N(1 <= N <= 250,000)开始,表示天数.在接下来的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; 
    }    
}

Answer 1

您正在寻找最大子阵列问题.
如维基百科所述,它可以在O(n)中求解.