上周，我在这里发布了一个问题，针对ACM ICPC东南区域赛 -> 算法计算某个二进制数范围内1的个数。它得到了很好的接待，并且仍未解决，所以我觉得为什么不提出另一个我的团队无法解决的问题呢。
问题如下：
他们在任何时间段内的最大利润为14，从第2天到第6天。 输入 每个测试用例的输入中将有多个测试用例。每个测试用例都以一个整数N（1 <= N <= 250,000）开头，表示天数。在接下来的N行中，每行都会有一个单独的整数P（-100 <= P <= 100），表示该天的利润。天数按顺序指定。输入将以一行单独的0结束。 输出 对于每个测试用例，输出一个整数，表示任何非空时间段的最大利润。将每个整数单独打印在自己的行上，不要在答案之间打印任何木板线。
问题如下：
你的朋友们刚刚开了一家新生意，你想看看他们做得如何。该企业已经营运了若干天，你的朋友记录了每天的净利润。你想找出你的朋友在至少一天连续时间段内取得的最大总利润。例如，如果你的朋友们的利润看起来像这样：
Day 1: -3
Day 2: 4
Day 3: 9
Day 4: -2
Day 5: -5
Day 6: 8
他们在任何时间段内的最大利润为14，从第2天到第6天。 输入 每个测试用例的输入中将有多个测试用例。每个测试用例都以一个整数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!)，这是不可接受的。我希望Stack Overflow可以做得更好。
祝你好运！
编辑
为了保持更新，这里是完成的代码，可以在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;
}
}
O(n^2)，而不是O(n!)。对于n天，存在恰好n(n+1)/2个可能的连续非空时间跨度。 - Steve Tjoa