最长正和子串

Question

我想知道怎样才能得到序列中最长的正和子序列：

例如，我有-6，3 -4，4 -5，所以最长的正子序列是3 -4。事实上，和是正的(3)，我们不能加-6或-5，否则它会变成负数。

它可以很容易地在O(N^2)中求解，我认为可以存在一些更快的东西，比如O(NlogN)

你有什么想法吗？

编辑:必须保留顺序，您可以跳过子字符串中的任何数字。

EDIT2:对不起，如果我用“substring”这个词引起了混乱，正如@beaker指出的，我指的是子字符串

Answer 1

O(n)空间和时间解决方案，将从代码开始(抱歉，Java ;-)，然后尝试解释它：

  public static int[] longestSubarray(int[] inp) {
    // array containing prefix sums up to a certain index i
    int[] p = new int[inp.length];
    p[0] = inp[0];
    for (int i = 1; i < inp.length; i++) {
      p[i] = p[i - 1] + inp[i];
    }

    // array Q from the description below
    int[] q = new int[inp.length];
    q[inp.length - 1] = p[inp.length - 1];
    for (int i = inp.length - 2; i >= 0; i--) {
      q[i] = Math.max(q[i + 1], p[i]);
    }

    int a = 0;
    int b = 0;
    int maxLen = 0;
    int curr;
    int[] res = new int[] {-1,-1};
    while (b < inp.length) {
      curr = a > 0 ? q[b] - p[a-1] : q[b];
      if (curr >= 0) {
        if(b-a > maxLen) {
          maxLen = b-a;
          res = new int[] {a,b};
        }
        b++;
      } else {
        a++;
      }
    }
    return res;
  }

• 我们操作的是大小为A的输入数组n。
• 让我们将数组P定义为包含前缀和的数组，直到索引i所以P[i] = sum(0,i)，其中‘i= 0,1，.，n-1’
• 让我们注意，如果u < v和P[u] <= P[v]，那么u永远不会是我们的终点
• 由于上述原因，我们可以定义一个数组Q，它包含Q[n-1] = P[n-1]和Q[i] = max(P[i], Q[i+1])
• 现在让我们来看看M_{a,b}，它向我们展示了从a开始，以b或更高结尾的最大和子数组。我们知道M_{0,b} = Q[b]和M_{a,b} = Q[b] - P[a-1]
• 有了上面的信息，我们现在可以初始化我们的a, b = 0并开始移动它们。如果M的当前值大于或等于0，那么我们知道我们将找到(或已经找到)一个带有和>= 0的子数组，然后我们只需要将b-a与先前找到的长度进行比较。否则，就没有从a开始并遵循约束的子数组，因此我们需要增加a。