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

Question

所以上周我在这里发布了 ACM ICPC South East Regionals 的问题 -> Algorithm to calculate the number of 1s for a range of numbers in binary .它很受欢迎，但仍未解决，所以我想为什么不提出另一个我的团队无法解决的问题。

问题。

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.

示例输入

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

样本输出

14
-19

---

如果您不担心效率，解决此问题的代码非常简单，但在比赛中解决该问题的唯一方法是 O(n!)，这是 Not Acceptable 。希望栈溢出能做得更好

祝你好运!

编辑

---

为了保持更新，这里提供了在 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

您正在寻找 Maximum Subarray Problem .
如维基百科所述，它可以在 O(n) 内求解。